1782. Сумма делителей

Пусть n – натуральное число. Число d является его делителем, если 1 ≤ d ≤ n и остаток от деления n на d равен нулю. По заданному числу n найдите сумму его делителей.

Вход. Одно целое число n (1 ≤ n ≤ 10¹⁸), все простые делители которого не превосходят 1000.

Выход. Выведите сумму делителей числа n.

Пример входа	Пример выхода
239	240

РЕШЕНИЕ

теория чисел

Анализ алгоритма

Обозначим через σ(n) сумму всех делителей числа n.

· Если n = p (p простое), то σ(n) = 1 + p;

· Если n = p^a (p простое), то σ(p^a) = 1 + p + p² + p³ + … + p^a = ;

Функция σ(n) является мультипликативной. Если n = , то

σ(n) = σ() * σ() * … * σ() =

Указанную сумму можно записать также в виде

σ(n) = = =

Пример

n = 239 простое, σ(239) = 1 + 239 = 240.

n = 24 = 2³ * 3, σ(24) = σ(2³) * σ(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, для которой i^a делит n.

while(n % i == 0)

{

n /= i;

p *= i;

}

После выполнения цикла p = i^a+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)