题目链接：Codeforces-803F-Coprime Subsequences
定义
f(i)
为以
i
为 gcd 的序列数，初始化
f(i)=2c(i)−1
，
c(i)
是以
i
为因子的数的个数。
直接加起来肯定有重复的部分，所以从后往前筛 f(i)=f(i)−∑i|df(d) 即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=
1e9+
7;
const int maxn=
1e5+
7;
ll p[maxn],f[maxn],ans;
int a[maxn],c[maxn],n,m,t;
int main()
{
cin>>m;
p[
0]=
1;
for(
int i=
1;i<=m;i++) p[i]=p[i-
1]*
2%mod;
for(
int i=
1;i<=m;i++)
cin>>t,++a[t],n=max(n,t);
for(
int i=
1;i<=n;i++)
{
int t=
0;
for(
int j=i;j<=n;j+=i) t+=a[j];
f[i]=p[t]-
1;
}
for(
int i=n;i;i--)
{
for(
int j=i*
2;j<=n;j+=i) f[i]=(f[i]-f[j]+mod)%mod;
ans=(ans+t)%mod;
}
cout << f[
1] << endl;
return 0;
}
