[SDOi2012]Longge的问题

（网上全部都是欧拉函数解法~~（甚至还有莫比乌斯反演？？））~~ 像我这种蒟蒻就真的想不到了。 我就用容斥解决了这道题。 既然要考虑gcd，而且不能暴力，就肯定要把n质因数分解了。 n=p1^q1 x p2^q2 x... x pk^qk #### gcd(a,b)的本质是：把a质因数分解，b质因数分解，对于每一个质因子，系数取min再相乘就是gcd 所以考虑一下n的所有因数。（远远不到sqrt（N）个，网上有说ln(n)??） 对于每一个因数p=p1^d1 x p2^d2 x... x pk^dk，它在n以内的倍数都有p， 但是，假设d1<q1时，同样是 p1^(d1+1) x p2^d2 x... * pk^dk的倍数的数，gcd就不是p了。 同理，每一个系数d如果能够加1，那么这个新因数的倍数们与n的gcd 就不是现在的p了。 我们把p的每一位的系数d分别能加1就加1，构造一个新数M，M的倍数就是一些不由p贡献的数。 把所有这些M的倍数减去，但是，最小公倍数们又减多了。再加上2个lcm，加上3个lcm们。。。。。。。 这就是容斥啦。 因为，2^32以内的一个数的不同质因子，最多只有10个（2x3x5x7x11x13x17x19x23x29 > 2^32） 所以，每次就2^10容斥一下，一定不会tle~！！！！！！！！！！！！！！ 就这样，两个dfs。一个枚举因数，一个用这个因数容斥。 复杂度上限：O（因数个数*（2^10）） 比网上一般的欧拉函数做法 O（因数个数* sqrt（n））的做法要快。 代码： ```cpp #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; } ```