Сума дільників#1782

Сума дільників (Розбір)

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

Якщо $n = p$ n = p, де $p$ — просте число, то у $n$ рівно два дільники: $1$ і $p$ . Отже

σ (n) = 1 + p

σ(n) = 1 + p

Якщо $n = p^{a}$ n = p^a, де $p$ — просте число і $a \geq 1$ a \ge 1, то всі дільники числа $n$ мають вигляд:

1, p, p^{2}, ..., p^{a}

1, p, p^2, ..., p^a

Їх сума утворює геометричну прогресію, тому

σ (p^{a}) = 1 + p + p^{2} + p^{3} + ... + p^{a} = \frac{p ^{a + 1} - 1}{p - 1}

σ(p^a) = 1 + p + p^2 + p^3 + ... + p^a = \frac{p^{a+1} - 1}{p - 1}

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

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

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

Нехай натуральне число $n$ має розклад на прості множники:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}},

n = p_1^{a_1} p_2^{a_2}...p_k^{a_k},

де $p_{1}, p_{2}, ..., p_{k}$ p_1, p_2, ..., p_k — різні прості числа.

Тоді, використовуючи мультиплікативність $σ (n)$ і формулу для степенів простих чисел, отримуємо:

σ (n) = σ (p_{1}^{a_{1}}) \cdot σ (p_{2}^{a_{2}}) \cdot ... \cdot σ (p_{k}^{a_{k}}) = \frac{p _{1}^{a_{1} + 1} - 1}{p _{1} - 1} \cdot \frac{p _{2}^{a_{2} + 1} - 1}{p _{2} - 1} \cdot ... \cdot \frac{p _{k}^{a_{k} + 1} - 1}{p _{k} - 1}

σ(n) = σ(p_1^{a_1}) \cdot σ(p_2^{a_2}) \cdot ... \cdot σ(p_k^{a_k}) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdot ... \cdot \frac{p_k^{a_k+1}-1}{p_k-1}

Зазначену суму можна записати також у вигляді

σ (n) = i = 1 \prod k \frac{p _{i}^{a_{i} + 1} - 1}{p _{i} - 1} = i = 1 \prod k (1 + p_{i} + p_{i}^{2} + \dots + p_{i}^{a_{i}}) = i = 1 \prod k j = 0 \sum a_{i} p_{i}^{j} .

\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1} = \prod_{i=1}^{k} \left( 1 + p_i + p_i^2 + \dots + p_i^{a_i} \right) = \prod_{i=1}^{k} \sum_{j=0}^{a_i} p_i^{\,j}.

Приклад

Число $n = 239$ n = 239 є простим, тобто має рівно два додатних дільники: $1$ і $239$ . За визначенням функції суми дільників отримуємо:

σ (239) = 1 + 239 = 240

σ(239) = 1 + 239 = 240

Розгляньмо число $n = 24$ n = 24. Його розклад на прості множники має вигляд:

24 = 2^{3} \cdot 3

24 = 2^3 \cdot 3

Оскільки числа $2^{3}$ 2^3 і $3$ взаємно прості, можна скористатися мультиплікативністю функції $σ (n)$ :

σ (24) = σ (2^{3}) \cdot σ (3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

σ(24) = σ(2^3) \cdot σ(3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

Обчислимо суму дільників для числа $n = 24$ n = 24 безпосередньо. Перелічимо всі додатні дільники числа $24$ :

1, 2, 3, 4, 6, 8, 12, 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

Зауважимо, що всі дільники можна згрупувати наступним чином:

σ (24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

σ(24) = \\ 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = \\ 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = \\ (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

Реалізація алгоритму

Читаємо вхідне значення $n$ .

scanf("%lld",&n);

У змінній $r es$ обчислюємо значення $σ (n)$ .

res = 1;

У змінній $i$ перебираємо всі прості дільники числа $n$ (за умовою задачі вони не перевищують $1000$ ). Для кожного такого дільника за формулою, виведеною в аналізі задачі, обчислюється внесок у суму дільників числа $n$ .

for (i = 2; i <= 1000; i++)
{
  p = i;

Нехай $i$ — простий дільник числа $n$ . Знайдемо найбільшу степінь $a$ , для якої $i^{a}$ i^a ділить $n$ .

  while(n % i == 0)
  {
    n /= i; 
    p *= i;
  }

Після завершення циклу отримуємо $p = i^{a + 1}$ p = i^{a+1}. Далі множимо поточне значення змінної $r es$ на $\frac{i ^{a + 1} - 1}{i - 1}$ \frac{i^{a + 1} - 1}{i - 1}.

  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();
  }
}

Java

Python реалізація

Читаємо вхідне значення $n$ .

n = int(input())

У змінній $r es$ обчислюємо значення $σ (n)$ .

res = 1

for i in range (2,1000) :
  p = i

Нехай $i$ — простий дільник числа $n$ . Знайдемо найбільшу степінь $a$ , для якої $i^{a}$ i^a ділить $n$ .

  while(n % i == 0) :
    n = n // i 
    p *= i

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

Виведемо відповідь.

print(res)