Codeforces803 F.Coprime Subsequences（容斥）

题意：

给定长度为n的序列， 问有多少个gcd为1的子序列。 答案对1e9+7取模。

数据范围：n<=1e5，a(i)<=1e5

解法：

$设f(i)为gcd为i的子序列数量$

$考虑容斥,先计算出gcd=i的倍数的数量,然后容斥掉gcd为i\ast 2,i\ast 3..的数量$

$设cnt[i]为序列中i的数量,那么f[i]=(2^{cnt[i]}-1)-f[i\ast 2]-f[i\ast 3]...$

$其中2^{cnt[i]-1}是从所有i的倍数中选出若干个数的方案数,$

$即C_{cnt[i]}^1+C_{cnt[i]}^2..C_{cnt[i]}^{cnt[i]}，因为不能取空集，因此减掉C_{cnt[i]}^0,$

$从后往前逆推即可$

code：

#include<bits/stdc++.h> using namespace std; #define int long long const int maxm=1e5+5; const int mod=1e9+7; int f[maxm]; int a[maxm]; int cnt[maxm]; int p2[maxm]; int n; signed main(){ p2[0]=1; for(int i=1;i<maxm;i++)p2[i]=p2[i-1]*2%mod; cin>>n; for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++; for(int i=1;i<maxm;i++){ for(int j=i+i;j<maxm;j+=i){ cnt[i]+=cnt[j]; } } for(int i=maxm-1;i>=1;i--){ f[i]=p2[cnt[i]]-1; for(int j=i+i;j<maxm;j+=i){ f[i]=(f[i]-f[j])%mod; } } cout<<(f[1]%mod+mod)%mod<<endl; return 0; }

---