Данная задача является упрощенным вариантом задания олимпиады KPI-OPEN 2018.
Задача
Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.
Входные данные
Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$
Выходные данные
Выведите сумму делителей числа $n.$
Тесты
| Входные данные | Выходные данные |
| $12$ | $28$ |
| $239$ | $240$ |
| $1234$ | $1854$ |
| $6$ | $12$ |
| $1000000007$ | $1000000008$ |
| $44100$ | $160797$ |
| $223092870$ | $836075520$ |
| $2147483648$ | $4294967295$ |
| $678906$ | $1471002$ |
| $1111111$ | $1116000$ |
| $9876543210$ | $27278469036$ |
| $99460729$ | $99470703$ |
| $5988$ | $14000$ |
| $1$ | $1$ |
| $1348781387$ | $1617960960$ |
| $135792$ | $406224$ |
| $5402250$ | $17041284$ |
| $375844500$ | $1259767236$ |
| $1000000000$ | $2497558338$ |
| $2357947691$ | $2593742460$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { long sumOfDivisors = 1; Scanner in = new Scanner(System.in); long n = in.nextLong(); HashMap<Long, Long> primeDivInPow = new HashMap<>(); for(long i = 2; i * i <= n; i++){ while(n % i == 0){ if(primeDivInPow.containsKey(i) == false){ primeDivInPow.put(i, (long) 1); } primeDivInPow.put(i, primeDivInPow.get(i) * i); n /= i; } } if(n != 1){ primeDivInPow.put(n, n); } for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) { sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1); } System.out.println(sumOfDivisors); } } |
Решение задачи
Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$