CF803F(莫比乌斯反演 + 容斥) （2000）

陌上 / 2023-05-04 / 原文

原题

题意：

给定一个n个数的序列，问你有多少个子序列的 gcd = 1。(n \(\le\) \(10^{5}\))

思路：

序列一共有n个数，则有 \(2^{n}\) - 1个子序列。
显然答案为 \(2^{n}\) - 1 减去 gcd > 1 的子序列的个数。

而问题来了———
gcd > 1的子序列的个数怎么求？

首先我们可以假设在这个长度为n的序列中gcd = 2的最长子序列长度为m，
那么同理必有 \(2^{m}\) - 1个gcd = 2的子序列。

假设原序列最大值为 ma
由此我们很容易想到枚举找出(gcd = 1 ~ m)的最长子序列的长度从而得到个数。

但是我们会发现 gcd = 2, gcd = 3的子序列会与gcd = 6的子序列发生重叠。
很明显考虑容斥原理奇加偶减，显然减去重叠后的答案为：
含有因子 2 的子序列个数（f2）+ 含有因子 3 的子序列个数（f3）+ 含有因子 6 的子序列个数（f6）- 含有因子 2,3 的子序列个数（f6）- 含有因子 2,6 的子序列个数（f12）-含有因子 3,6 的子序列个数（f18）+ 含有因子 2,3,6 的子序列个数（f36）
但是如果我们用二进制枚举选与不选的状态，则时间复杂度为 \(2^{n}\)，显然不可行。
因此我们引入莫比乌斯函数 \(\mu\)(n)

则答案为 \(2^{n}\) - 1 +\(\quad \sum_{i=2}^{ma}\mu(i)\times\)\(f_i\)

AC代码

const int N = 1e5 + 10;
int cnt, primes[N], mob[N];
int a[N], p2[N], cntt[N];
bool st[N];

// 莫比乌斯函数
void init(int n)  // 线性筛质数并保存mob[x]的值
{
    p2[0] = 1; p2[1] = 2;
    mob[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        p2[i] = (p2[i-1] * 2ll + mod) % mod;  // O(n)预处理 2^i
        if (!st[i]) primes[cnt ++ ] = i, mob[i] = -1;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) 
            {
                mob[t] = 0;
                break;
            }
            mob[t] = mob[i] * (-1);
        }
    }
}

void solve()
{
    int n,ma = 0;
    cin >> n;
    rep(i,1,n)
    {
        cin >> a[i];
        ma = max(ma,a[i]);  // 取序列最大值
        cntt[a[i]] ++;  // cntt[x]:记录x在序列中出现的次数
    }
    
    int ans = p2[n] - 1;  // ans为答案
    
    for(int i = 2; i <= ma; i ++)
    {
        int num = 0;  // 序列中i的所有倍数的个数
        for(int j = i; j <= ma; j += i)
        {
            num = (num + cntt[j]) % mod;
        }
        ans = (ans + mob[i] * (p2[num] - 1) % mod + mod) % mod;  // 容斥相加
    }
    cout << ans << endl;
}