2480. Longge's problem
Longge is good at
mathematics and he likes to think about hard mathematical problems which will
be solved by some graceful algorithms. Now a problem comes: Given an integer n (1 < n < 231), you are to calculate ∑gcd(i, n)
1 ≤ i ≤ n.
"Oh, I know, I
know!" Longge shouts! But do you know? Please solve it.
Input. Input contain several test case.
A number n per line.
Output. For each n output ∑gcd(i,
n) 1 ≤ i ≤ n a line
Sample Input
2
6
Sample
Output
3
15
РЕШЕНИЕ
теория чисел
Анализ алгоритма
НОД(i * j, n)
= НОД(i, n) * НОД(j, n), следовательно функция f(x) = НОД(x, n) мультипликативна.
Пусть g(n) =
. Тогда g(
) = g(
) * g(
) * … * g(
).
Теорема. Для любого простого p и натурального a имеет
место соотношение:
g(pa)
= (a + 1)pa – apa–1
Доказательство.
При а = 1
имеем: g(p) = НОД(1, p) + НОД(2, p) + … + НОД(p, p) = (p – 1) + p = 2p – 1.
Аналогично при а
= 2:
g(p2)
= НОД(1, p2) + НОД(2, p2) + … + НОД(p, p2)
+
+ НОД(p + 1,
p2) + … + НОД(2p, p2)
+ … + НОД(p2, p2) =
= (1 + 1 + … + 1 + p)
+ (1 + 1 + … + 1 + p) + … + (1 + 1 +
… + 1 + p2) =
= (p2
– p) + p (p – 1) + p2 = 3p2 – 2p
Пример
Пусть n = 6.
Тогда g(6) = 
=
= НОД(1, 6) + НОД(2, 6) + НОД(3, 6) + НОД(4, 6) +
НОД(5, 6) + НОД(6, 6) =
= 1 + 2 +3 + 2 + 1 + 6 = 15
Вычислим g(6) исходя из мультипликативности функции f(x) = НОД(x, n):
g(6) = g(2) * g(3) = (2*2 – 1) * (2*3 – 1) = 3 * 5 =
15
Реализация алгоритма
#include <stdio.h>
#include <math.h>
long long i, n, res, a, p;
int main(void)
{
while(scanf("%lld",&n) == 1)
{
res = 1;
for(i = 2;
i * i <= n; i++)
{
if(n % i
== 0)
{
a = 0; p = 1;
while(n
% i == 0)
{
a++;
p *= i;
n /= i;
}
res *= (a + 1) * p - a * p / i;
}
}
if (n >
1) res *= (2*n - 1);
printf("%lld\n",res);
}
return 0;
}