枫林晚 的博客

枫林晚 的博客

[SDOi2012]Longge的问题

posted on 2018-07-26 15:15:20 | under 未分类 |

(网上全部都是欧拉函数解法(甚至还有莫比乌斯反演??))

像我这种蒟蒻就真的想不到了。

我就用容斥解决了这道题。

既然要考虑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))的做法要快。

代码:

#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;
}