CF803F
场上死磕无法战胜，原来是个绿题吗哈哈。
考虑到跟序列的顺序无关，直接在值域上做。我们设 \(f_i\) 表示 \(\gcd = i\) 的方案数。那么有
\[f_i = 2^{g_i} - 1 - \sum_{i | d \land i \ne d} f_d
\]
\(g_i\) 是原序列中是 \(i\) 倍数的个数。那么调和级数 \(O(V\log V)\) 预处理 \(g\)，同复杂度计算 \(f\)，答案是 \(f_1\)。
#include<bits/stdc++.h>
#define _fo(a, b, c) for(int b = a; b >= c; b--)
#define fo(a, b, c) for(int b = a; b <= c; b++)
#define mod 1000000007
#define N 100010
using namespace std;
int cnt[N], a[N], n, p[N], f[N], Max;
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin >> n;fo(1, i, n) cin >> a[i], cnt[a[i]]++, Max = max(Max, a[i]);p[0] = 1;fo(1, i, n) p[i] = p[i - 1] * 2 % mod;_fo(Max, i, 1){int sum = 0;for(int j = i; j <= Max; j += i) sum += cnt[j];f[i] = (p[sum] - 1 + mod) % mod;for(int j = i * 2; j <= Max; j += i) f[i] = (f[i] - f[j] + mod) % mod;}cout << f[1];return 0;
}