[SDOi2012]Longge的问题
枫林晚
2018-07-26 15:15:20
(网上全部都是欧拉函数解法~~(甚至还有莫比乌斯反演??))~~
像我这种蒟蒻就真的想不到了。
我就用容斥解决了这道题。
既然要考虑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;
}
```