题解 P3172 【[CQOI2015]选数】

Shadows · 2018-01-20 16:31:17 · 题解

这题还可以莫比乌斯反演做

图摘自GXZlegend的blog

mu函数的前缀合使用杜教筛求，先预处理一部分，可以取阈值为2e6左右

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<map>
    #define maxn 2000020
    #define mod 1000000007
    #define logn 11
    #define inf (1<<30)
    using namespace std;
    int n,k,l,h,prime[maxn/logn],sum[maxn],tot;
    bool vis[maxn];
    map<int,int>sum2;
    int power(int a,int kkk){
        int ans=1;
        for(;kkk;kkk>>=1,a=(1ll*a*a)%mod)
        if(kkk&1)ans=(1ll*ans*a)%mod;
        return ans;
    }
    void init(){
        memset(prime,0,sizeof(prime));
        memset(vis,0,sizeof(vis));
        memset(sum,0,sizeof(sum));
        sum[1]=1;
        tot=0;
        for(int i=2;i<maxn;++i){
            if(!vis[i])sum[i]=-1,prime[++tot]=i;
            for(int j=1;j<=tot&&(i*prime[j])<maxn;++j){
                vis[i*prime[j]]=1;
                if(!(i%prime[j])){
                    sum[i*prime[j]]=0;
                    break;
                }
                sum[i*prime[j]]=-sum[i];
            }
        }
        for(int i=1;i<maxn;++i)sum[i]+=sum[i-1];
        scanf("%d%d%d%d",&n,&k,&l,&h);
    }
    int Sum(int x){
        if(x<maxn)return sum[x];
        if(sum2.find(x)!=sum2.end())return sum2[x];
        long long s=1;
        int la;
        for(int i=1;i<=(x>>1);i=la+1){
            la=x/(x/i);
            s-=(Sum(la)-Sum(i-1))*(x/i-1ll);
        }
        return sum2[x]=s%mod;
    }
    void solve(){
        int ans=0,la;
        l=(l-1)/k,h/=k;
        for(int i=1;i<=h;i=la+1){
            la=min(h/(h/i),l/i?(l/(l/i)):inf);
            ans=(ans+(1ll*(Sum(la)-Sum(i-1))*power(h/i-l/i,n))%mod)%mod;
        }
        printf("%d\n",(ans+mod)%mod);
    }
    int main(){
        init();
        solve();
        return 0;
}