Делители произведения, (олимпиадная задача) Опции

[Айра]

Зональная олимпиада по информатике.
Задача 2. "делители произведения"(20 баллов)
Задано N натуральных чисел a1,a2,...,aN (1<=N<=20), каждое из которых находится в интервале от 1 до 10000.
Необходимо определить количество натуральных делителей произведения a1*a2*...*aN.
Требуется написать программу, которая вычисляет количество натуральных делителей произведения вышеназванного числа.
Входные данные
Натуральное число N. Числа a1,a2,...,aN, записанные через пробел.
Выходные данные
Число натуральных делителей
Пример:
Вход:
4
3 5 7 720
Выход:
120

Мое решение:

program z2(input,output);
uses wincrt;
label m1;
var k,n: integer;
    p,i: longint;
    a: array[1..10000] of integer;
begin
       p:=1;
       k:=0;
m1: writeln ('введите количество чисел');
       readln (n);
       if (n<=0) or (n>=21) then
       begin
            writeln ('число должно быть в интервале от 1 до 20');
            goto m1;
       end;
       writeln ('введите значения чисел');
       for i:=1 to n do
       begin
            read (a[i]);
            p:=p*a[i];
       end;
            for i:=1 to p do
       begin
            if p mod i=0 then k:=k+1;
       end;
writeln (k);
end.

Если что, не судите строго. Я не волшебник, а только учусь.

[Malice]

Мое решение:
, не судите строго. Я не волшебник, а только учусь.

Произведение 20 чисел от 1 до 10к это еденица с 80-тью нулями, что точно не влезет в longint

[Айра]

В этом проблема, а типа с большим диапазоном нет (по крайней мере в моей книге). Может там какое-то другое решение...

М

Обсуждение продолжается здесь, когда оно закончится - в теме "Олимпиадные Задачи" появится ссылка на этот топик...

[Malice]

В этом проблема, а типа с большим диапазоном нет (по крайней мере в моей книге). Может там какое-то другое решение...

Такие задачи в лоб не решаются, это ж очевидно. Раз мы не можем записать такое число, то можно представить его в виде произведения простых множителей (сперва разложить сами числа и сложить их степени), а уж оттуда должно получится искомое число..

[Malice]

Вот где-то так получилось:

const n=4;
const a:array [1..n] of longint= (3,5,7,720);
var i,j,k,l,z:longint;
b:boolean;
begin
k:=1;
z:=a[1];
for i:=2 to n do if a[i]>z then z:=a[i];
for i:=2 to round(sqrt(z)) do begin
b:=false;
for j:=2 to i-1 do b:=b or (i mod j=0);
if not(b) then begin
z:=0;
for j:=1 to n do begin
l:=i;
while (a[j] mod l)=0 do begin l:=l*i; inc(z); end;
end;
k:=k*(z+1);
end; end;
writeln (k);
end.

[Michael_Rybak]

А можно без проверки на простоту (только если массив не константный):

...
k := 1;
for i := 2 to 10000 do begin
  z := 0;
  for j := 1 to n do
    while a[j] mod i = 0 do begin
      a[j] := a[j] div i;
      Inc(z);
    end;
  k := k * (z + 1);
end;
...

Только вот лонгинта не всегда будет хватать

[Айра]

В принципе, я поняла как надо было делать. Спасибо всем!
Только вот что такое round:

for i:=2 to round(sqrt(z)) do

Сообщение отредактировано: Айра - 15.12.2006 19:02

[Malice]

Округление до целого типа.

[Айра]

Еще раз спасибо! Теперь мне все ясно, как и то, что на олимпиаде мне делать было нечего.