CF803F Coprime Subsequences(容斥)

考虑先求出最大公约数大于 $1$ 的子序列个数

显然,我们可以枚举这个最大公约数

我们预处理一个 $ok[i]$ 表示有 $ok[i]$ 个数字含有约数 $i$

然后我们去枚举子序列的最大公约数 $x$ 来计算答案

我们定义 $f[i]$ 表示最大公约数是 $i$ 倍数的方案数

$f[i]=2^{ok[i]}-1$

怎么求最大公约数是 $i$ 的方案数呢??

我们定义 $g[i]$ 表示最大公约数是 $i$ 的方案数

那么 $g[i]=f[i]-g[2i]-g[3i]-g[4i]$

预处理 $ok$ 数组的复杂度,直接质因子分解的话是 $O(n\sqrt{m})$

采用调和级数的处理方式复杂度是 $O(nlog(m)\ )$

转移 $g$ 数组是调和级数的复杂度

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+10;
const int mod = 1e9+7;
int n,a[maxn],ok[maxn],f[maxn],g[maxn];
int quick(int x,int n)
{
    int ans = 1;
    for( ; n ; n>>=1,x=x*x%mod )
        if( n&1 )    ans = ans*x%mod;
    return ans;
}
signed main()
{
    cin >> n;
    for(int i=1;i<=n;i++)    cin >> a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=a[i];j++)
        {
            if( a[i]%j!=0 )    continue;
            ok[j]++;
            if( j!=a[i]/j )    ok[a[i]/j]++;
        }
    }
    for(int i=2;i<=100000;i++)    f[i] = quick( 2,ok[i] )-1;
    for(int i=100000;i>=2;i--)
    {
        g[i] = f[i];
        for(int j=i+i;j<=100000;j+=i)    g[i] -= g[j];
    }
    int ans = quick(2,n)-1;
    for(int i=2;i<=100000;i++)    ans = ( ans-g[i] )%mod;
    cout << ( ans%mod+mod )%mod;
}