Помощь - Поиск - Пользователи - Календарь
Полная версия: Делители произведения
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Айра
Зональная олимпиада по информатике.
Задача 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.



Если что, не судите строго. Я не волшебник, а только учусь. rolleyes.gif
Malice
Цитата(Айра @ 11.12.2006 20:58) *

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

Произведение 20 чисел от 1 до 10к это еденица с 80-тью нулями, что точно не влезет в longint smile.gif
Айра
В этом проблема, а типа с большим диапазоном нет (по крайней мере в моей книге). Может там какое-то другое решение... smile.gif

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

Malice
Цитата(Айра @ 11.12.2006 23:41) *

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

Такие задачи в лоб не решаются, это ж очевидно. Раз мы не можем записать такое число, то можно представить его в виде произведения простых множителей (сперва разложить сами числа и сложить их степени), а уж оттуда должно получится искомое число..
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;
...


Только вот лонгинта не всегда будет хватать smile.gif
Айра
В принципе, я поняла как надо было делать. Спасибо всем! smile.gif
Только вот что такое round:
Цитата
for i:=2 to round(sqrt(z)) do unsure.gif
Malice
Округление до целого типа.
Айра
Еще раз спасибо! Теперь мне все ясно, как и то, что на олимпиаде мне делать было нечего. smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.