简要题意
纳塔国有 n 座城市，城市 i 的“魅力值”为 a_i。城市 i 与城市 j 之间存在一条有向边，当且仅当 i<j 且 \gcd(a_i,a_j)\neq 1。
你需要求出从城市 1 出发到达城市 n 的路径数。答案对 998,244,353 取模。
## 思路
不是，CF 2000 的题目也开始考莫反了？
不妨先 dp，设 $f_i$ 表示从 $1$ 到达 $i$ 的路径数，显然有 $f_1=1$，且：
$$
f_i=\sum_{j=1}^{i-1}[\gcd(a_i,a_j)\neq 1]f_j
$$
时间复杂度 $O(n^2\log a_i)$ 难以承受。
观察到后面那个东西很像莫反，先将式子变形得：
$$
f_i=\sum_{j=1}^{i-1}[\gcd(a_i,a_j)\neq 1]f_j=\sum_{j=1}^{i-1}f_j - \sum_{j=1}^{i-1}[\gcd(a_i,a_j)=1]f_j
$$
考察后面的和式（因为前面的和式很好做），套用经典结论 $\mu\ast 1=\epsilon$ 得：
$$
\sum_{j=1}^{i-1}[\gcd(a_i,a_j)=1]f_j=\sum_{j=1}^{i-1}f_j\sum_{d\mid a_i,d\mid a_j}\mu(d)=\sum_{d\mid a_i}\mu(d)\sum_{d\mid a_j}f_j
$$
考虑转移的时候直接枚举 $d$，开个桶记录一下 $g(d)=\sum_{d\mid a_j}f_j$ 即可。
时间复杂度 $O(a_i\log a_i+n\sum d(a_i))$。由于 $\max d(a_i)=240$，所以可以通过本题。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }
const int N = 2e5 + 5, M = 1e6 + 5;
int n, pri[N], tot, mu[M], a[N], g[M];
vector<int> d[M];
bool vis[M];
void sieve(int n){
mu[1] = 1;
for(int i=2;i<=n;i++){
if(!vis[i]) mu[i] = mod - 1, pri[++tot] = i;
for(int j=1;j<=tot&&1ll*i*pri[j]<=n;j++){
vis[i * pri[j]] = 1;
if(!(i % pri[j])) break;
mu[i * pri[j]] = mod - mu[i];
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i) d[j].emplace_back(i);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
sieve(*max_element(a + 1, a + n + 1));
int sumt = 1, f = 0;
for(int j : d[a[1]]) g[j] = 1;
for(int i=2;i<=n;i++){
int tmp = 0;
for(int j : d[a[i]]) tmp = Add(tmp, Mul(mu[j], g[j]));
f = Sub(sumt, tmp);
sumt = Add(sumt, f);
for(int j : d[a[i]]) g[j] = Add(g[j], f);
}
cout << f << '\n';
return 0;
}
// Written by xiezheyuan
```