bzoj2705 Pillai函数

发表于   |  

fractal128讲过了，我把推倒写一下。

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Sol

设$$s(k) = \{m | gcd(m, n) = k \}$$
$$g(k) = |s(k)|$$
因为 $$gcd(m, n) = k$$
所以 $$gcd(m/k, n/k) = 1$$
所以 $$s(k) = {m | gcd(m/k, n/k) = 1}$$
即 $$g(k) = \phi(n/k) $$
$$\sum gcd(i, N) = \sum k * \phi(n/k) $$
//MathJax 没有什么是不能用斜杠解决的，如果有，就用两个。

Code

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
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#define filenamein "1.in"
#define filenameout "1.out"
typedef long long ll;
using namespace std;
ll read(){
    ll x = 0, f = 1; char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') f = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0'){ x = x * 10 + ch -'0'; ch = getchar();}
    return x*f;
}
ll n, ans = 0;
ll phi(ll x){
	ll t = x, ret = x;
	for (ll i = 2; i * i <= x; i++)
	if (!(t % i)) {
		ret = ret / i * (i - 1);
		while (!(t % i)) t /= i;
	}
	if (t > 1) ret = ret / t * (t - 1);
	return ret;
}
int main(){
    freopen(filenamein, "r", stdin);
    freopen(filenameout, "w", stdout);
    n = read();
    for (ll i = 2; i * i <= n; i++){
    	if (!(n % i)){
    		ans += n / i * phi(i);
    		if (i * i != n) ans += i * phi(n / i);
    	}
    }
    printf("%lld\n", ans+n+phi(n));
    return 0;
}