CodeForces - 803F： Coprime Subsequences（莫比乌斯&容斥）

Let's call a non-empty sequence of positive integers a₁, a₂... a_k 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 10⁹ + 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 a₁, a₂... a_n (1 ≤ a_i ≤ 100000).

Output

Print the number of coprime subsequences of a modulo 10⁹ + 7.

Examples

Input

3
1 2 3

Output

Input

4
1 1 1 1

Output

Input

7
1 3 5 15 3 105 35

Output

题意：给定N个数，问有多少个子序列，其GCD=1。

思路：我们枚举GCD=g的倍数，那么是是g的倍数的个数为X的时候，其贡献是pow(2,X)-1。加上容斥，前面加一个莫比乌斯系数即可。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep2(i,a,b) for(int i=a;i<b;i++)

using namespace std;

const int maxn=;

const int Mod=1e9+;

int num[maxn],p[maxn],vis[maxn],mu[maxn],cnt,ans;

vector<int>G[maxn];

int qpow(int a,int x){

    int res=; while(x){

        if(x&) res=(ll)res*a%Mod;

        x>>=; a=(ll)a*a%Mod;

    } return res;

}

void prime()

{

    mu[]=; rep(i,,maxn-) G[i].push_back();

    for(int i=;i<maxn;i++){

        if(!vis[i]) p[++cnt]=i,mu[i]=-;

        for(int j=i;j<maxn;j+=i) G[j].push_back(i);

        for(int j=;j<=cnt&&p[j]*i<maxn;j++){

            mu[i*p[j]]=-mu[i]; vis[i*p[j]]=;

            if(i%p[j]==){mu[i*p[j]]=; break;}

        }

    }

}

int main()

{

    prime() ;int N,x;

    scanf("%d",&N);

    rep(i,,N){

        scanf("%d",&x);

        rep2(j,,G[x].size()) num[G[x][j]]++;

    }

    rep(i,,) ans=((ans+mu[i]*(qpow(,num[i])-))%Mod+Mod)%Mod;

    printf("%d\n",ans);

    return ;

}

巴特西

CodeForces - 803F： Coprime Subsequences（莫比乌斯&容斥）

最新文章

热门文章