Пусть n – натуральное число. Число d является его делителем, если 1 ≤
d ≤ n и остаток от деления n
на d равен нулю. По заданному числу n
найдите сумму его делителей.
Вход. Одно целое число n (1 ≤ n ≤ 1018),
все простые делители которого не превосходят 1000.
Выход. Выведите сумму делителей числа n.
Пример входа |
Пример выхода |
239 |
240 |
теория
чисел
Обозначим через σ(n) сумму всех делителей числа n.
·
Если n = p (p простое), то σ(n) = 1 + p;
·
Если n = pa (p простое), то σ(pa) = 1 + p + p2 + p3
+ … + pa = ;
Функция σ(n) является мультипликативной. Если n = , то
σ(n) = σ() * σ(
) * … * σ(
) =
Указанную сумму можно записать также в виде
σ(n) = =
=
n = 239 простое,
σ(239) = 1 + 239 = 240.
n = 24 = 23
* 3, σ(24) =
σ(23) * σ(3) =
(1 + 2 + 4 + 8) * (1 + 3) = 15 * 4 = 60.
Вычислим сумму делителей для n = 24 непосредственно:
σ(24) =
1 + 2 + 3 + 4 + 6 + 8 + 12 + 24
=
1 + 2 +
4 + 8 + 3 * (1 + 2 + 4 + 8) =
(1 + 2 +
4 + 8) * (1 + 3) = 15 *
4 = 60
Читаем входное значение n.
scanf("%lld",&n);
res = 1;
В переменной i перебираем все простые делители
числа n (по условию задачи они не более 1000). Вычисляем сумму делителей
числа n по указанной в анализе задачи формуле.
for(i = 2; i <= 1000; i++)
{
p = i;
Пусть i – простой делитель n.
Находим максимальную степень a, для которой ia делит n.
while(n % i
== 0)
{
n /= i;
p *= i;
}
После выполнения цикла p = ia+1.
Умножаем res на .
res *= (p - 1) / (i - 1);
}
Выводим ответ.
printf("%lld\n",res);
Python реализация
n
= int(input())
res
= 1
for i
in range (2,1000) :
p = i
while(n % i
== 0) :
n = n // i
p *= i
res *= (p - 1) //
(i - 1)
print
(res)