https://codeforces.com/contest/2037/problem/G

#include <iostream>
#include <vector>
#include <queue>
#include <iterator>
#include <sstream>
#include <algorithm>
#include <ranges>
#include <cmath>
#include <set>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define int long long
signed main(){
    int n;
    std::cin>>n;
    int max=1e6+10;
    std::vector<bool> notPrime(max,false);
    std::vector<int>pri;
    std::vector<int> mu(max);
    for(int i=2;i<max;++i){
        if (!notPrime[i]){
            pri.emplace_back(i);
            mu[i]=1;
        }
        for(auto&e:pri){
            if (i*e>=max)break;
            notPrime[i*e]= true;
            if (i%e==0)break;
            mu[i*e]=-mu[i];
        }
    }
    int mod=998244353;
    std::vector<int>dp(n+1);
    std::vector<int> count(max);
    dp[0]=1;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin>>x;
        for(int j=1;j*j<=x;++j){
            if (x%j==0){
                dp[i]=(dp[i]+(mu[j]*count[j])%mod)%mod;
                if (j*j<x){
                    dp[i]=(dp[i]+(mu[x/j]*count[x/j])%mod)%mod;
                }
            }
        }
        for (int j = 1; j*j <=x ; ++j) {
            if (x%j==0){
                count[j]=(count[j]+dp[i])%mod;
                if (j*j<x){
                    count[x/j]=(count[x/j]+dp[i])%mod;
                }
            }
        }
    }
    std::cout<<(dp[n-1]%mod+mod)%mod<<'\n';
    return 0;
}

题目大意：

有1-n个节点，每个节点有权值ai,当且仅当
i<ji<j and gcd(ai,aj)≠1gcd(ai,aj)≠1
两节点有单向边连接

问从1-n的通路个数

思路：

考虑将小于当前节点i的节点的通路个数作为状态，将可达的节点的状态求和转移到当前节点，

现在解决快速决定两节点间是否有边

注意到，两节点间有相同的因数就一定有相同的质因数，两节点有相同的n个不同的质因数就一定有这相同的质因数积作为因数

根据the Principle of Inclusion-Exclusion,我们只需要计算有一个相同质因数的所有点-两个相同质因数的点+三个相同质因数的点...........就可以快速进行状态转移

最后有一个小技巧：因为会出现较小值-较大值，所以结果需要保证非负(dp[n-1]%mod+mod)%mod