3.Задано N естественных чисел a1,a2,,aN ( ), каждое из которых находится
3.Задано N натуральных чисел a1,a2,,aN ( ), каждое из которых находится в интервале от 1 до 10000. Нужно найти количество естественных делителей творения a1*a2**aN.
надобно написать программку на си
1 ответ
Алиса Мочалина
includelt;stdio.hgt;
int main()
int div[10001];
int i,d,n,x;
long int p = 1;
for(i = 0; i lt; 10000; i++)
div[i] = 1;
scanf("%d",amp;n);
for(i = 0; i lt; n; i++)
scanf("%d",amp;x);
d = 2;
while(d lt;= x)
while(x%d == 0)
x /= d;
div[d]++;
d++;
for(i = 0; i lt; 10000; i++)
p *= div[i];
printf("%ld",p);
return 0;
/*
Небольшое объясненье:
Мысль решения содержится в том, что любой делитель результата представим как творение обычных чисел в определенных ступенях. Тогда набор этих ступеней однозначно определяет подходящий делитель. Наибольшая степень, с которой может быть взято простое число, является суммой ступеней, с которыми оно заходит в множители.
Для простоты массив вхождений делителей задан от 0 до 10000, но т.к. перебор делителей множителей идет по возрастанию, учтены будут только обыкновенные делители.
Пример:
10 * 8 * 9 = 720
10 = 2^1*5^2
8 = 2^3
9 = 3^2
Т.е. число 2 заходит в творение в четвертой ступени, 3 - во 2-ой, 5 - в первой.
Означает хоть какой делитель числа 720 представим (единственным образом) в виде
2^(d2) * 3^(d3) * 5^(d5), где d2 = 0..4, d3 = 0..2, d5 = 0..1
К примеру, 1 = 2^0 * 3^0 * 5^0, 720 = 2^4 * 3^2 * 5^1
Есть 5 способов избрать d2 (0,1,2,3,4), 3 метода выбрать d3 и 2 метода избрать d5 --gt; всего 5 * 3 * 2 = 30 вероятных наборов --gt; 30 делителей у числа 720
(если какое-то число не возникает среди делителей множителей, то его можно брать только одним методом - со ступенью 0 - что не влияет на ответ)
*/
int main()
int div[10001];
int i,d,n,x;
long int p = 1;
for(i = 0; i lt; 10000; i++)
div[i] = 1;
scanf("%d",amp;n);
for(i = 0; i lt; n; i++)
scanf("%d",amp;x);
d = 2;
while(d lt;= x)
while(x%d == 0)
x /= d;
div[d]++;
d++;
for(i = 0; i lt; 10000; i++)
p *= div[i];
printf("%ld",p);
return 0;
/*
Небольшое объясненье:
Мысль решения содержится в том, что любой делитель результата представим как творение обычных чисел в определенных ступенях. Тогда набор этих ступеней однозначно определяет подходящий делитель. Наибольшая степень, с которой может быть взято простое число, является суммой ступеней, с которыми оно заходит в множители.
Для простоты массив вхождений делителей задан от 0 до 10000, но т.к. перебор делителей множителей идет по возрастанию, учтены будут только обыкновенные делители.
Пример:
10 * 8 * 9 = 720
10 = 2^1*5^2
8 = 2^3
9 = 3^2
Т.е. число 2 заходит в творение в четвертой ступени, 3 - во 2-ой, 5 - в первой.
Означает хоть какой делитель числа 720 представим (единственным образом) в виде
2^(d2) * 3^(d3) * 5^(d5), где d2 = 0..4, d3 = 0..2, d5 = 0..1
К примеру, 1 = 2^0 * 3^0 * 5^0, 720 = 2^4 * 3^2 * 5^1
Есть 5 способов избрать d2 (0,1,2,3,4), 3 метода выбрать d3 и 2 метода избрать d5 --gt; всего 5 * 3 * 2 = 30 вероятных наборов --gt; 30 делителей у числа 720
(если какое-то число не возникает среди делителей множителей, то его можно брать только одним методом - со ступенью 0 - что не влияет на ответ)
*/
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
найти порядковый номер 41Э если в ядре 20 нейтронов
Разные вопросы.
в ряду натуральных чисел 3, 8, 10, 24, … 18 одно
Математика.
Предприятие по производству с/хоз продукции на производство затратило 3527000 руб Валовый
Разные вопросы.
Математика, задано на каникулы. ВАРИАНТ 1004
НОМЕР 1,2,3,4,5,6,7,8.
Математика.
Имеются три конденсатора емкостью С1=1мкФ, С2=2мкФ и С3=3мкФ. Какую наименьшую емкость
Физика.
Из точки м выходят 3 луча MP MN и MK причём
Геометрия.
выпиши в свою тетрадь те правила этикета которые тебе не были
Разные вопросы.
Анна хорошо учится у неё много подруг свободное от учёбы время
Обществознание.
10) Килограмм конфет дороже килограмма печенья на 52 р. За 8
Математика.
Во сколько раз число атомов кислорода в земной коре больше числа
Химия.
Облако тегов