题解：CF2037G Natlan Exploring

观察到 \gcd(i, j) 总是 i 中一个或多个质因子倍数，而 a_i\leq 1000000，本质不同的质因子只有 7 个，于是可以容斥。

具体思路如下：

每一轮取出 a_i，找到所有质因子，枚举每个选或者不选，然后预处理 pre_k 表示 \sum\limits_{j\in [1, i-1], a_j | k} f_j，那么枚举完每个选或者不选后，当前情况可以 O(1) 解答，算完 f_i 后遍历所有因子更改 pre。

时间复杂度 O(n\times\sqrt{a_i}+2^{w(1000000)}\cdot n)，其中 w(1000000)=7，可以通过。

代码：

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n;
int a[1000005], f[1000005], pre[1000005];
vector <int> z[1000005], zz[1000005];
const int mod = 998244353;
signed main () {
    cin >> n;
    For (i, 1, n) {
        cin >> a[i];
        z[i].push_back (a[i]);
        int x = sqrt (a[i]);
        for (int j = 2; j <= x; j ++) {
            if (a[i] % j == 0) {
                z[i].push_back (j);
                if (j * j != a[i]) z[i].push_back (a[i] / j);
            }
        }
        int t = a[i];
        for (int j = 2; j <= x; j ++) {
            if (t % j == 0) {
                zz[i].push_back (j);
                while (t % j == 0) t /= j;
            }
        }
        if (t != 1) zz[i].push_back (t);
    }
    f[1] = 1;
    for (int j : z[1]) pre[j] = (pre[j] + 1) % mod;
    For (i, 2, n) {
        int sz = zz[i].size ();
        for (int j = 1; j < (1 << sz); j ++) {
            int num = 1, cnt = 0;
            For (k, 0, sz - 1) {
                if (j & (1 << k) ) {
                    num = num * zz[i][k];
                    ++ cnt;
                }
            }
            if (cnt & 1) f[i] = (f[i] + pre[num]) % mod;
            else f[i] = (f[i] - pre[num] + mod) % mod;
        }
        for (int j : z[i]) pre[j] = (pre[j] + f[i]) % mod;
    }
    cout << f[n];
    return 0;
}

卡空间差评，害我吃罚时。