Coprime Subsequences

题意：
给你一个长度为n的序列，让你求序列的最大公约数为1的子序列数目为多少？

思路：
莫比乌斯反演
首先统计一下该序列有什么数，个数为多少。
然后求莫比乌斯函数。
统计有i为因子的数有x。
根据x求都有该因子的序列有 ( )个
根据莫比乌斯函数判断该序列数是加上还是减去.
最后得出结果.

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;
const int N=2e5+5;

ll x,mu[N], ma[N];

ll dp[N], prime[N], ji=0, pa[N];

int main()
{
    int n;
    ll m=0;
    cin>>n;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]*2%inf;
    }
    for(int i=1;i<=n;i++)
    {
            cin>>x;
            m=max(m,x);
            ma[x]++;
    }
    mu[1]=1;
    pa[1]=1;
    for(ll i=2;i<=m;i++)
    {
        if(!pa[i])
        {
            prime[ji++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<ji;j++)
        {
            if(i*prime[j]>m)
            {
                break;
            }
            pa[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            else
            {
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        ll s=0;
        for(int j=1;j*i<=m;j++)
        {
            s+=ma[i*j];
        }
        ans=(ans+(mu[i]*(dp[s]-1)%inf+inf)%inf)%inf;
    }
    cout<<ans<<'\n';
    return 0;
}