题目
给出一个正整数序列,求有多少子序列的gcd不为1。
求解
假设子序列gcd为x,那么只需求出x的倍数的数量m,gcd为x的子序列数量即为
2
m
−
1
2^m-1
2m−1。
这样可以求出 gcd分别为2的倍数、3的倍数、4的倍数… 的方案数,剩下的就是容斥了,比如6,计算2的倍数、3的倍数的时候重复算了,那么要减去。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int mul[N];
int a[N];
int get(int x)
{
map<int, int> mp;
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
while (x % i == 0)
{
mp[i]++;
if (mp[i] >= 2)
return 0;
x /= i;
}
}
}
if (x >= 2)
mp[x]++;
return mp.size() & 1 ? -1 : 1;
}
void init() //预处理莫比乌斯(也可以欧拉筛线性处理
{
mul[1] = 1;
for (int i = 2; i < N; i++)
mul[i] = get(i);
}
int tong[N], num[N];
const long long mod = 1e9 + 7;
long long qpow(long long a, long long b)
{
long long res = 1;
while (b)
{
if (b & 1)
{
res = res * a % mod;
}
b /= 2;
a = a * a % mod;
}
return res;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
tong[a[i]]++;
}
for (int i = 2; i <= 1e5; i++)
for (int j = i; j <= 1e5; j += i)
num[i] += tong[j]; //num[i]表示i的倍数有多少个
long long ans = 0;
for (int i = 2; i <= 1e5; i++) //莫比乌斯容斥
ans = (ans - mul[i] * (qpow(2, num[i]) - 1) % mod + mod) % mod;
cout << ans << endl;
}
int main()
{
init();
solve();
return 0;
}