「BZOJ2705」[SDOI2012]Longge的问题

Description

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

Input

一个整数,为NN

Output

一个整数,为所求的答案。

Sample Input

1
6

Sample Output

1
15

HINT

0<N2320<N\leq 2^{32}

Solution

gcd(i,n)(1in)\sum gcd(i,n)(1\leq i\leq n)等价于求iϕ(ni)(1in)\sum i \cdot \phi(\frac{n}{i})(1\leq i\leq n)
对于ini\leq \sqrt{n},直接枚举ii,并且直接求ϕ(ni)\phi(\frac{n}{i})
对于i>ni>\sqrt{n},枚举ni\frac{n}{i},那么就是求ϕ(i)\phi(i),直接求答案

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

ll n;
int t;
int phi[65556], b[65556], tot;
bool vis[65556];
void shai() {
phi[1] = 1;
for(int i = 2; i <= t; ++i) {
if(!vis[i]) b[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot && b[j] <= t / i; ++j) {
vis[i * b[j]] = 1;
if(i % b[j] == 0) {
phi[i * b[j]] = phi[i] * b[j];
break;
} else phi[i * b[j]] = phi[i] * phi[b[j]];
}
}
}
ll get(ll x) {
if(x == 0) return 0;
ll res = x;
for(int i = 1; i <= tot && x > b[i]; ++i) if(x % b[i] == 0){
while(x % b[i] == 0) x /= b[i];
res = res * (b[i] - 1) / b[i];
}
if(x > 1) res = res * (x - 1) / x;
return res;
}
int main() {
n = read();
t = sqrt(n);
shai();
ll ans = 0;
for(int i = 1; i <= t; ++i) if(n % i == 0)
ans += phi[i] * (n / i);
for(int i = 1; i <= t; ++i) if(n % i == 0 && i * i != n)
ans += get(n / i) * i;
writeln(ans);
return 0;
}