题解：CF2037G Natlan Exploring

这不是我们 ARC185E 吗。

考虑沿用那一题的做法对于一个 a_i 把他的非零因数上都加上 f_i，这样的话对于一个 a_j，我们去遍历他的非零因数并且希望只会在 \gcd(a_i,a_j) 处得到一个 f_i 的贡献，考虑容斥。

我们维护一个容斥系数 v_i，满足 \sum_{d|i\land d\ne 1}v_d=1，那么有 v_i=1-\sum_{d|i\land d\ne 1\land d\ne i} v_d，这显然可以 O(n\ln n) 做。

正确性的话你考虑对于每个 i 假如它是应该被当成 \gcd 造成贡献的数，按照上面的方法，他的每个因数都会被当成 \gcd 造成贡献，那么因为 \sum_{d|i\land d\ne 1}v_d=1 的性质，所以多余贡献就被消掉了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define N 1000005
#define LL long long
#define MOD 998244353

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,a[N]; LL f[N],g[N],val[N];

int main() {
    n=R();
    for (int i=1;i<=n;i++) a[i]=R();
    for (int i=2;i<=N;i++) {
        val[i]=1-val[i];
        for (int j=2*i;j<N;j+=i) val[j]+=val[i];
    }
    f[1]=1;
    for (int i=1;i<n;i++) {
        for (int j=1;j*j<=a[i];j++)
            if (a[i]%j==0) {
                if (j!=1) (g[j]+=f[i])%=MOD;
                if (j!=a[i]/j) (g[a[i]/j]+=f[i])%=MOD;
            }
        for (int j=1;j*j<=a[i+1];j++)
            if (a[i+1]%j==0) {
                if (j!=1) (f[i+1]+=1ll*val[j]*g[j]%MOD)%=MOD;
                if (j!=a[i+1]/j) (f[i+1]+=1ll*val[a[i+1]/j]*g[a[i+1]/j]%MOD)%=MOD;
            }
    }
    W((f[n]+MOD)%MOD,'\n');
    return 0;
}

容易发现 v_i=-\mu(i)，因为我们有 \sum_{d|i} \mu(d)=\varepsilon(i)，当 i\ne 1 时有 \sum_{d|i\land i\ne 1}-\mu(d)=1-\varepsilon(i)=1。