数学、暴力枚举、容斥原理、最大公约数与最小公倍数
现在发现我确实有利用性质的意识，但是这性质我没找到。
神秘智慧暴力题，看题解来的。
首先这不是图论题，容易想到维护 $w_{a_i}$ 为到达所有值为 $a_i$ 的位置的方案数之和，每次枚举所有和 $a_i$ 不互质的数计算到达 $a_i$ 的方案数 $sum$，然后令 $w_{a_i} \leftarrow w_{a_i} + sum$，这样做的时间复杂度为 $O(nV)$。考虑优化，注意到更新 $w_{a_i}$ 的时间复杂度为 $O(1)$ 而查询的时间复杂度为 $O(V)$，考虑标记 $a_i$ 的所有因数，查询时也仅查询 $a_i$ 的所有因数。发现这会导致算重，我的思考过程在这里结束。
考虑利用性质，题目中 $a_j$ 能贡献到 $a_i$ 当且仅当 $j<i$ 且 $\gcd(a_j,a_i) \neq 1$，不在意 $\gcd(a_j,a_i)$ 的值，只需保留 $a_i,a_j$ 的本质不同质因子（所有质因子的指数对 $1$ 取 $\min$）。具体地，若 $a_i = 12 = 2^2 \times 3^1$，则将 $a_i$ 的值修改为 $2 \times 3 = 6$，因为正整数 $x$ 满足 $\gcd(x,12) \neq 1$ 当且仅当 $\gcd(x,6) \neq 1$。
在保留所有元素的本质不同质因子之后，序列中任何两个元素的 $\gcd$ 也至多包含某个质因子一次，现在要求 $a_j$ 能贡献到 $a_i$ 恰好一次。初始化 $sum=0$，枚举 $a_i$ 除 $1$ 外的所有因子 $k$，若 $k$ 的本质不同质因子数量为奇数则令 $sum \leftarrow sum + w_k$，否则令 $sum \leftarrow sum - w_k$，考虑该做法的正确性。
若 $\gcd(a_i,a_j)$ 不为 $1$，由于 $\gcd(a_i,a_j) = p_1^{b_1} p_2^{b_2} \cdots p_{m}^{b_m}$（算术基本定理）且元素的每个质因子只保留一次，所以 $\forall i \in [1,n] \cap \mathbb{Z},b_i = 1$。上述计算过程等价于进行 $m$ 元容斥，能够正确计算 $a_j$ 对 $a_i$ 的贡献。由于 $a_j$ 可以任意选取，所以这个算法可以正确计算 $a_1 \sim a_{i-1}$ 中每个值对 $a_i$ 的贡献。
计算完毕 $sum$ 的值之后再次枚举 $a_i$ 除 $1$ 外的所有质因子 $k$，令 $w_k \leftarrow w_k +sum$ 即可。
分析时间复杂度，$10^6$ 以内的本质不同质因子最多的数为 $510510 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17$，容斥的计算量级至多为 $2^7 = 128$，将容斥的计算量记为 $k$。处理本质不同质因子需要 $O(V)$ 预处理后 $O(\log V)$ 更新一个值，总体时间复杂度 $O(n \log V + nk + V)$。
#include<bits/stdc++.h>
using namespace std;
constexpr int lim=1'000'000,mod=998'244'353;
int n,cnt,top,s[10],a[200'005],d[1'000'005],p[1'000'005];
Mint<mod> w[1'000'005];
bitset<1'000'005> on;
Mint<mod> dfscal(int x,int now,int cho){
if(x>top) return cho&1 ? w[now]:0-w[now];
return dfscal(x+1,now,cho)+dfscal(x+1,now*s[x],cho+1);
}
Mint<mod> calculate(int x){
Mint<mod> ret(0);
for(top=0;x!=1;x/=d[x]) if(top==0||s[top]!=d[x]) s[++top]=d[x];
return dfscal(1,1,0);
}
void dfsupd(int x,int now,Mint<mod> add){
if(x>top) return w[now]+=add*(now!=1),void();
dfsupd(x+1,now,add),dfsupd(x+1,now*s[x],add);
}
void update(int x,Mint<mod> add){
for(top=0;x!=1;x/=d[x]) if(top==0||s[top]!=d[x]) s[++top]=d[x];
dfsupd(1,1,add);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for(int i=2;i<=lim;i++){
if(!on[i]) p[++cnt]=i,d[i]=i;
for(int j=1;j<=cnt&&i*p[j]<=lim;j++){
on[i*p[j]]=1,d[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
update(a[1],Mint<mod>(1));
for(int i=2;i<=n-1;i++){
Mint<mod> x=calculate(a[i]);
update(a[i],x);
}
cout<<calculate(a[n])<<'\n';
return 0;
}