Задача
Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $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 |
#include <iostream> #include <map> using namespace std; int main () { long long n, sumOfDivisors = 1; cin >> n; map<long long, long long> primeDivInPow; for(long long i = 2; i * i <= n; i++){ while(n % i == 0){ if(primeDivInPow.find(i) == primeDivInPow.end()){ primeDivInPow[i] = 1; } primeDivInPow[i] *= i; n /= i; } } if(n != 1){ primeDivInPow[n] = n; } for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){ sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1); } cout << sumOfDivisors; return 0; } |
Решение задачи
Пусть $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}.$$