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

 

Пусть 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);

 

Java реализация

 

import java.util.*;

 

class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    long n = con.nextLong();

    long res = 1;

    for(int i = 2; i <= 1000; i++)

    {

      long p = i;

      while(n % i == 0)

      {

        n /= i;

        p *= i;

      }

      res *= (p - 1) / (i - 1);

    }

 

    System.out.println(res);

    con.close();

  }

}

 

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)