526互联

F. Coprime Subsequences 莫比乌斯反演

发布时间 2023-09-16 01:22:08作者: 久远寺冇珠

 题意：

在洛谷想练练莫反，遇到了这题，所以直接用洛谷的翻译吧

 不是我懒，感觉人确实翻译的好。

做法：

很套路性的把函数 f(n),F(n)定义如下。

（我比较习惯用latex）

再根据莫比乌斯反演，我们可以推出

然后我们发现，ans=f(1)。求即可。在求的过程中我还是有个地方没想到。就是求F(i)的时候，1e5的数据定然不好枚举，记忆中也没有过相应的trick，但是我校的骄傲wlm先生恰好写过这题，他的代码长这样：

        for(int j=i;j<maxn;j+=i)
            res+=cnt[j];

然后我们就可以愉快的ac了

bool vis[N];
int prim[N],mu[N],sum[N],cnt;
void get_mu(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]){mu[i]=-1;prim[++cnt]=i;}
        for(int j=1;j<=cnt&&i*prim[j]<=n;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)break;
            else mu[i*prim[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i];
}
void solve(){
    int n;cin>>n;
    int ans=0ll;
    vector<int>a(n+1);
    vector<int>num(100010);
    int mm=0ll;
    for(int i=1;i<=n;i++){
        cin>>a[i];num[a[i]]++;
        mm=max(mm,a[i]);
    }
    for(int i=1;i<=mm;i++){
        for(int j=2*i;j<=mm;j+=i)
            num[i]+=num[j];
    }
    for(int i=1;i<=mm;i++){
        int temp=binpow(2ll,num[i],mod);
        temp=(temp-1+mod)%mod;
        ans=kplus(ans,kx(mu[i],temp));
    }
    cout<<ans<<"\n";

}