Версия для печати темы

Автор: Айра 12.12.2006 0:58

Зональная олимпиада по информатике.
Задача 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 12.12.2006 1:23

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

Автор: Айра 12.12.2006 3:41

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

М

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

Автор: Malice 12.12.2006 4:20

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

Автор: Malice 13.12.2006 21:33

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

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 13.12.2006 22:11

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

...
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;
...

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

Автор: Айра 15.12.2006 19:01

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

Автор: Malice 15.12.2006 19:04

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

Автор: Айра 16.12.2006 0:29

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