Solution

设 dp_i 表示到 i 的方案数。很明显的转移：dp_i=\displaystyle\sum_{j=1}^{i-1}dp_j[\gcd(a_i,a_j)\ne 1]，初始化 dp_1=1，答案为 dp_n。

设 s_i=\displaystyle\sum_{j=1}^i dp_j，那么 dp_i=s_{i-1}-\displaystyle\sum_{j=1}^{i-1}dp_j[\gcd(a_i,a_j)=1]。

直接上莫比乌斯反演：dp_i=s_{i-1}-\displaystyle\sum_{j=1}^{i-1}dp_j\sum_{k\mid\gcd(a_i,a_j)}\mu(k)。

所以枚举 a_i 的因数 k，打个桶对 k 累加 j\in[1,i) 且 k\mid a_j 的贡献 dp_j。

莫比乌斯函数值可提前预处理得到，每个数的所有约数直接根号暴力枚举。

时间复杂度：O(n\sqrt V)。

Code

#include<bits/stdc++.h>
const int mod=998244353;
int mu[1000005];
int sum[1000005];
int n;
int main(){
    mu[1]=1;
    for(int i=1;i<=500000;++i)
        if(mu[i])
            for(int j=i<<1;j<=1000000;j+=i)
                mu[j]-=mu[i];
    scanf("%d",&n);
    for(int i=1,pre=0,dp,x;i<=n;++i){
        scanf("%d",&x);
        dp=(i==1?-1:0);
        for(int j=1;j*j<=x;++j)
            if(!(x%j)){
                if(mu[j])mu[j]==1?(dp+=sum[j])>=mod&&(dp-=mod):(dp-=sum[j])<0&&(dp+=mod);
                if(j*j!=x&&mu[x/j])mu[x/j]==1?(dp+=sum[x/j])>=mod&&(dp-=mod):(dp-=sum[x/j])<0&&(dp+=mod);
            }
        if((dp=pre-dp)<0)dp+=mod;
        if(i==n)return 0&printf("%d",dp);
        for(int j=1;j*j<=x;++j)
            if(!(x%j)){
                (sum[j]+=dp)>=mod&&(sum[j]-=mod);
                if(j*j!=x)(sum[x/j]+=dp)>=mod&&(sum[x/j]-=mod);
            }
        if((pre+=dp)>=mod)pre-=mod;
    }
    return 0;
}