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

 

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

 

Вход. Одно натуральное число n (1 ≤ n ≤ 1018). Известно, что все простые делители числа n не превосходят 1000.

 

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

 

Пример входа

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

239

240

 

 

РЕШЕНИЕ

теория чисел

 

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

Рассмотрим функцию σ(n), которая по положительному целому числу n возвращает сумму всех его положительных делителей.

·        Если n = p, где p – простое число, то у n ровно два делителя: 1 и p. Следовательно

σ(n) = 1 + p

·        Если n = pa, где p – простое число и a ≥ 1, то все делители числа n имеют вид:

1, p, p2, …, pa

Их сумма образует геометрическую прогрессию, поэтому

σ(pa) = 1 + p + p2 + p3 + … + pa =

 

Функция σ(n) является мультипликативной, то есть для любых взаимно простых чисел x и y выполняется равенство:

σ(xy) = σ(x) σ(y)

 

Пусть натуральное число n имеет разложение на простые множители:

n  = ,

где p1, p2, …, pk – различные простые числа.

Тогда, используя мультипликативность σ(n) и формулу для степеней простых чисел, получаем:

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

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

σ(n) =  =  =

 

Пример

Число n = 239 является простым, то есть имеет ровно два положительных делителя: 1 и 239. По определению функции суммы делителей получаем:

σ(239) = 1 + 239 = 240

 

Рассмотрим число n = 24. Его разложение на простые множители имеет вид:

24 = 23 * 3

Поскольку числа 23 и 3 взаимно просты, можно воспользоваться мультипликативностью функции σ(n):

σ(24) = σ(23) * σ(3) = (1 + 2 + 4 + 8) * (1 + 3) = 15 * 4 = 60.

 

Вычислим сумму делителей для числа n = 24 непосредственно. Перечислим все положительные делители числа :

1, 2, 3, 4, 6, 8, 12, 24

Сложим их:

σ(24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 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 вычисляем значение σ(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.

 

n = int(input())

 

В переменной res вычисляем значение σ(n).

 

res = 1

 

В переменной i перебираем все простые делители числа n (по условию задачи они не превосходят 1000). Для каждого такого делителя по формуле, выведенной в анализе задачи, вычисляется вклад в сумму делителей числа n.

 

for i in range (2,1000) :

  p = i

 

Пусть i – простой делитель числа n. Найдём наибольшую степень a, для которой ia делит n.

 

  while(n % i == 0) :

    n = n // i

    p *= i

 

После завершения цикла получаем p = ia+1. Далее умножаем текущее значение переменной res на .

 

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

 

Выводим ответ.

 

print(res)