Задача
Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.
Входные данные
Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$
Выходные данные
Выведите сумму делителей числа $n.$
Тесты
| Входные данные | Выходные данные |
| $100000000000031$ | $100000000000032$ |
| $10000019$ | $10000020$ |
| $400001520001444$ | $700002730002667$ |
| $9$ | $13$ |
| $304250263527210$ | $1281001468723200$ |
| $94083986096100$ | $457766517350961$ |
| $1234567898765$ | $1517681442816$ |
| $100000000000000$ | $249992370597277$ |
| $562949953421312$ | $1125899906842623$ |
| $81795$ | $161280$ |
| $9999999999999$ | $14903272088640$ |
| $997$ | $998$ |
| $1325$ | $1674$ |
| $2468013$ | $3290688$ |
| $951641320$ | $2447078400$ |
| $71675429738641$ | $71695352830464$ |
| $1100000000033$ | $1200000000048$ |
| $6300088$ | $11859480$ |
| $98$ | $171$ |
| $9102837465$ | $15799834440$ |
Код программы
|
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 - 1) / (p -> first - 1) + p -> second; } 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}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$