【CodeForces】915 G. Coprime Arrays 莫比乌斯反演

【题目】G. Coprime Arrays

【题意】当含n个数字的数组的总gcd=1时认为这个数组互质。给定n和k，求所有sum(i),i=1~k，其中sum(i)为n个数字的数组，每个数字均<=i，总gcd=1的方案数。n<=2*10^6。答案将所有sum(i)处理成一个数字后输出。

【算法】数论（莫比乌斯反演）

【题解】假设当前求sum(k)，令f(i)表示gcd=i的数组方案数，F(i)表示i|gcd的数组的方案数。

因为F(x)=Σ_x|df(d)，由莫比乌斯反演定理，f(x)=Σ_x|dμ(d/x)*F(d)。

又F(x)=(k/x)^n，所以f(1)=Σμ(d)*(k/d)^n，d=1~k。

初始k=1，当k++时ans+=Σ_d|kμ(d)*((k/d)^n-(k/d-1)^n)，这个过程只需要k ln k枚举贡献答案即可，同时预处理快速幂。

复杂度O(k log n+k ln k)。

#include<cstdio>

const int N=,MOD=1e9+;

int n,m,miu[N],prime[N],mark[N],sum[N],p[N],tot,ans,ANS;

int pow(int x,int k){

    if(!x)return ;

    int ans=;

    while(k){

        if(k&)ans=1ll*ans*x%MOD;

        x=1ll*x*x%MOD;

        k>>=;

    }

    return ans;

}

int main(){

    scanf("%d%d",&n,&m);

    miu[]=;

    for(int i=;i<=m;i++){

        if(!mark[i]){miu[prime[++tot]=i]=-;}

        for(int j=;j<=tot&&i*prime[j]<=m;j++){

            mark[i*prime[j]]=;

            if(i%prime[j]==)break;

            miu[i*prime[j]]=-miu[i];

        }

    }

    for(int i=;i<=;i++)p[i]=pow(i,n);

    for(int i=;i<=m;i++){

        for(int j=i;j<=m;j+=i)sum[j]=((sum[j]+1ll*miu[i]*(p[j/i]-p[j/i-]))%MOD+MOD)%MOD;

        ans=(ans+sum[i])%MOD;

        ANS=(ANS+(ans^i))%MOD;

    }

    printf("%d",ANS);

    return ;

}

巴特西

【CodeForces】915 G. Coprime Arrays 莫比乌斯反演

最新文章

热门文章