Educational Codeforces Round 20 F. Coprime Subsequences(莫比乌斯反演)

Dear 丶 2022-06-16 12:24 167阅读 0赞

题目链接：  
[点击我打开题目链接][Link 1]  
题意：  
给你一个序列，问你有多少个子序列的gcd（子序列）=1。

题解：  
考虑一下容斥，枚举gcd然后容斥，先加上所有子序列的总个数2n−1，然后减去gcd=2的，然后减去gcd=3的，然后减去gcd=5的，然后加上gcd=6的….为什么不减去gcd=4呢？  
因为这些的贡献统计到gcd=2了，减去gcd=2就包含了。 f(i) 为以 i 为gcd 的序列数，那么f(i)=2cnt(i)−1 ，cnt(i) 是以 i 为因子的数的个数，然后你发现这个东西就是莫比乌斯反演，直接线性筛。  
然后快速统计含有某个数的作为因子的数有多少个。因为这时考虑的约数就在\[1,100000\]这里面。O(N−−√)考虑每个数的约数即可。

代码：

#include <bits/stdc++.h>
    using namespace std;
    const int mod=1e9+7;
    const int maxn=123456;
    typedef long long ll;
    int mu[maxn],prime[maxn],cnt[maxn],Pow[maxn];
    int vis[maxn];
    int n;
    int total;
    void shai()
    {
        mu[1] = 1; //固定的
        for (int i = 2; i <= maxn; i++)
        {
            if (!vis[i])  //是素数
            {
                prime[++total] = i; //记录，之后要用到 
                mu[i] = -1;  //质因数分解个数为奇数
            }
            for (int j = 1; j <= total; j++)//质数或者合数都进行的
            { 
                if (i * prime[j] > maxn) break;
                vis[i * prime[j]] = 1;
                if (i % prime[j] == 0) 
                {
                    mu[prime[j] * i] = 0;
                    break;
                }
                mu[prime[j] * i]  = - mu[i];
                //关键，使得它只被最小的素数筛去。例如i等于6的时候。
                //当时的素数只有2,3,5。6和2结合筛去了12，就break了
                //18留下等9的时候，而9*2=18筛去
            }
        }
    }
    int main()
    {
        ll ans = 0 ;
        int x;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            for(int j=1;j*j<=x;j++)
            {
                if(x%j==0){
                    cnt[j]++;
                    if(j!=x/j)
                    {
                        cnt[x/j]++;     
                    }
                }
            }
        }
        Pow[0]=1;
        for(int i=1;i<maxn;i++)
        {
            Pow[i]=(Pow[i-1]*2)%mod;
        }
        shai();
        for(int i=1;i<maxn;i++)
        {
            ans = (ans + (Pow[cnt[i]]-1)*mu[i])%mod;
        }
        ans=(ans+mod)%mod;
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://codeforces.com/contest/803/problem/F