题意：
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
对于100%的数据，0<N<=2^32
题解：
（网上全部都是欧拉函数解法（甚至还有莫比乌斯反演？？））
像我这种蒟蒻就真的想不到了。
我就用容斥解决了这道题。
既然要考虑gcd，而且不能暴力，就肯定要把n质因数分解了。
n=p1^q1 * p2^q2 *... * pk^qk
gcd(a,b)的本质是：把a质因数分解，b质因数分解，对于每一个质因子，系数取min再相乘就是gcd
所以考虑一下n的所有因数。（远远不到sqrt（N）个，网上有说ln(n)??）
对于每一个因数p=p1^d1 * p2^d2 *... * pk^dk，它在n以内的倍数都有p，
但是，假设d1<q1时，同样是 p1^(d1+1) * p2^d2 *... * pk^dk的倍数的数，gcd就不是p了。
同理，每一个系数d如果能够加1，那么这个新因数的倍数们与n的gcd 就不是现在的p了。
我们把p的每一位的系数d分别能加1就加1，构造一个新数M，M的倍数就是一些不由p贡献的数。
把所有这些M的倍数减去，但是，最小公倍数们又减多了。再加上2个lcm，加上3个lcm们。。。。。。。
这就是容斥啦。
因为，2^32以内的一个数的不同质因子，最多只有10个（2*3*5*7*11*13*17*19*23*29 > 2^32）
所以，每次就2^10容斥一下，一定不会tle~！！！！！！！！！！！！！！
就这样，两个dfs。一个枚举因数，一个用这个因数容斥。
复杂度上限：O（因数个数*（2^10））
比网上一般的欧拉函数做法 O（因数个数* sqrt（n））的做法要快。
（2018.8.10补充：而且，对于gcd(n,1~m)的和,其中m远远大于n，也可以这样做！！！网上的方法就不行了。）
（upda：2019.3.22:之前太辣鸡了，反演是容斥的超集）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; ll has[20],cnt; ll ans; struct node{ ll num,mi; }c[20]; ll tot;//sum of primes ll sum=0; void sol(){ ll k=n; for(ll i=2;i*i<=n;i++){ if(k%i==0){ c[++tot].num=i; while(k%i==0) c[tot].mi++,k/=i; } } if(k!=1) c[++tot].num=k,c[tot].mi++; } void dfs1(int x,int cnt,ll digi){ if(x==tot+1){ if(cnt&1) sum-=n/digi; else sum+=n/digi; return; } dfs1(x+1,cnt,digi); if(has[x]<c[x].mi) dfs1(x+1,cnt+1,digi*c[x].num); } void dfs2(int x,ll now){ if(x==tot+1){ sum=0; dfs1(1,0,now); ans+=sum*now; return; } ll to=1; for(int i=0;i<=c[x].mi;i++){ has[x]=i; dfs2(x+1,now*to); to*=c[x].num; } } int main() { scanf("%lld",&n); sol(); dfs2(1,1); printf("%lld",ans); return 0; }