题意

给你n个数让你从中挑选一个非空子序列，使得子序列

问有多少个这样的非空子集

解析

我太菜了理解了好久这个容斥

首先来说就是正着求我们不好求 那么我们就去反过来求 把所有的 减去不等于1的

那么来分析一下有哪些不等于1的情况

简单来说就是有两个以上的数字他们有着一个相同的因子，那个因子就可以是

比如3 6 15 就有一个相同的因子3 所以他们这里就有个非空子序列

所以我们只要找到所有的这个 然后用总的减去不等于1的

我们统计每一个的因子

即计算这些数中有多少个数字包含因子

然后我们可以求出公约数为的序列数就等于

为什么要减去 因为我们在计算有多少个数字包含的时候，也给的里面增加了一个，先看代码 然后在代码里再解释这个

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

ll n , m;
ll p[N];
int cnt[N];
int a[N];

int main(void){
    cin>>n;
    p[0] = 1;
    for(int i = 1 ; i <= n ; ++i){
        p[i] = (p[i - 1] << 1) % MOD;
        int x ;
        cin>>x;
        for(int j = 1 ; j * j <= x ; ++j){
            if(x % j == 0){
                cnt[j]++;
                if(j * j == x)  continue;
                cnt[x / j]++;
            }
        }
    }
    for(int i = 1 ; i < N - 7; ++i){
        a[i] = (p[cnt[i]] - 1) % MOD;
    }
    for(int i = N - 7 ; i >= 1 ; --i){
        for(int j = i + i ; j <= N -7 ; j += i){
            a[i] = (a[i] - a[j] + MOD) % MOD;
        }
    }

    cout<<a[1]<<endl;
    return 0;
}

看代码就能看到

举例

6

1 2 3 4 5 6

我们在统计6的时候 给2也加上了一个 但是这个明显是用不了的 所以要减去