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

https://www.cnblogs.com/onioncyc/p/8288709.html

 裸算是O(m*根号m)  然后观察一下可以知道本次的一部分可以由上一层的一部分更新而来

【题解】假设当前求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)。

最初级的想法应该是先预处理出来每个数的因子，然后for(i=1;i<=m;++i) for(int j=0;j<yin[i].size();++j) sum+=(i/yin[i][j])^n-(i/yin[i][j]-1)^n这样，sum代表的是差量，然后还要加一个ans记录当前的值,最后ans+=sum这样子，然后这么些有点麻烦，然后发现有些因子是重复用了很多次，干脆就枚举因子算了，然后此时sum就得用一个sum数组代表每个i与i-1的差量了，因为枚举因子的话，做不到i是空间上连续,所以不能只用一个单一变量sum

#include<cstdio>
const int N=2000010,MOD=1e9+7;
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 0;
    int ans=1;
    while(k){
        if(k&1)ans=1ll*ans*x%MOD;
        x=1ll*x*x%MOD;
        k>>=1;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    miu[1]=1;
    for(int i=2;i<=m;i++){
        if(!mark[i]){miu[prime[++tot]=i]=-1;}
        for(int j=1;j<=tot&&i*prime[j]<=m;j++){
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)break;
            miu[i*prime[j]]=-miu[i];
        }
    }
    for(int i=0;i<=2000000;i++)p[i]=pow(i,n);
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j+=i)sum[j]=((sum[j]+1ll*miu[i]*(p[j/i]-p[j/i-1]))%MOD+MOD)%MOD;
        ans=(ans+sum[i])%MOD;
        ANS=(ANS+(ans^i))%MOD;
    }
    printf("%d",ANS);
    return 0;
}