题意

给定一正整数序列 ，问有多少个非空子序列使得其中所有数的 为 1。

题解

容斥，设 为 为 的倍数，的非空子序列个数。那么如果 中有 个数是 的倍数那么 。

设 为 恰为 的非空子序列个数。那么 。

时间复杂度 ，其中 。

#include <bits/stdc++.h>
#define MOD 1000000007
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
int n, a[100005], cnt[100005] = {0};
int cntb[100005] = {0};
const int m = 100000;
int ans[100005];
void init(){
    n = read();
    REP(i, 1, n) a[i] = read(), ++cnt[a[i]];
    REP(i, 1, m)
        for (int j = i; j <= m; j += i)
            cntb[i] += cnt[j];
}
void solve(){
    REPR(i, m, 1){
        ans[i] = modadd(poww(2, cntb[i]), MOD - 1);
        for (int j = i + i; j <= m; j += i)
            ans[i] = modadd(ans[i], MOD - ans[j]);
    }
    printf("%d\n", ans[1]);
}
int main(){
    init();
    solve();
    return 0;
}