F. Coprime Subsequences
题目链接：
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Let's call a non-empty sequence of positive integers a1, a2... ak coprime if the greatest common divisor of all elements of this sequence is equal to 1.
Given an array a consisting of n positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo 109 + 7.
Note that two subsequences are considered different if chosen indices are different. For example, in the array [1, 1] there are 3 different subsequences: [1], [1] and [1, 1].
Input
The first line contains one integer number n (1 ≤ n ≤ 100000).
The second line contains n integer numbers a1, a2... an (1 ≤ ai ≤ 100000).
Output
Print the number of coprime subsequences of a modulo 109 + 7.
Examples
input
3
1 2 3
output
5
input
4
1 1 1 1
output
15
input
7
1 3 5 15 3 105 35
output
100
题意：给一个序列，问gcd为1的子序列有多少个;
思路：容斥，可以求出gcd为1的倍数的子序列个数，然后减去gcd为2,3,5,等等一个素数倍数的子序列个数再加上两个素数积倍数的子序列个数以此类推，
（注意容斥里面集合的交集里面不可能有4,9,12这种数，因为质因数分解后里面同一个质因数的个数>1，这就不可能在两个集合的交集里面）；
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
const int mod=1e9+7;
int n,a[maxn],p[maxn];
int vis[maxn],num[maxn];
void init()
{
p[0]=1;
for(int i=1;i<maxn;i++){p[i]=p[i-1]*2;if(p[i]>=mod)p[i]-=mod;}
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
num[i]++;
for(int j=2*i;j<maxn;j+=i)
{
vis[j]=1;
if(num[j]==-1)continue;
int tep=j,x=0;
while(tep%i==0)x++,tep/=i;
if(x>1)num[j]=-1;
else num[j]++;
}
}
}
}
int main()
{
init();
scanf("%d",&n);
int x;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
for(int j=1;j*j<=x;j++)
{
if(x%j)continue;
a[j]++;
if(j*j!=x)a[x/j]++;
}
}
int ans=0;
for(int i=1;i<maxn;i++)
{
if(num[i]==-1)continue;
if(num[i]&1)ans=(ans-p[a[i]]+1);
else ans=(ans+p[a[i]]-1);
if(ans>=mod)ans-=mod;
else if(ans<0)ans+=mod;
}
printf("%d
",ans);
return 0;
}