原题
题意：
给定一个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;
}