AT_ndpc2026_l 最小公倍数 题解

· · 题解

有一些对 这篇题解 的补充说明。

首先朴素的转移是容易的，令 f_i 表示 1 \to i 的路径数，那么有：

f_i = \sum_{j<i} f_j \text{lcm} (a_i, a_j)

可以接近 O(n^2) 转移，考虑优化。

\begin{align} f_i &= \sum_{j<i} f_j \frac{a_ia_j}{\gcd(a_i, a_j)} \\ &= a_i \sum_{j<i} \frac{f_j a_j}{\gcd(a_i, a_j)} \\ \end{align}

这里有一个经典 trick，把 \gcd 拆成若干个因子贡献和，即 \frac{1}{\gcd(x,y)} = \sum\limits_{d \mid x \land d \mid y} \mu(d)。

考虑 \mu(x) 怎么算，因为这个函数满足 \sum\limits_{d \mid x} \mu(d) = \frac{1}{x}，可以推一下式子：

\begin{align} \sum_{d \mid x} \mu(d) &= \frac{1}{x} \\ \mu(x) &= \frac{1}{x} - \sum_{d \mid x \land d \ne x} \mu(d) \end{align}

预处理每个数的因子，就可以 O(n \log n) 递推，于是就有：

\begin{align} f_i &= a_i \sum_{j<i} \frac{f_j a_j}{\gcd(a_i, a_j)} \\ &= a_i \sum_{j<i} \left(f_j a_j \sum_{d \mid a_i \land d \mid a_j} \mu(d)\right) \\ &= a_i \sum_{j<i} \sum_{d \mid a_i \land d \mid a_j} f_j a_j \mu(d) \\ &= a_i \sum_{d \mid a_i} \sum_{j < i \land d \mid a_j} f_j a_j \mu(d) \\ \end{align}

然后这里还有一个小 trick，我们记录每个 d 对于 f_i 的贡献函数 g_{i,d}，即：

g_{i,d} = \sum_{j<i \land d \mid a_j} f_j a_j \mu(d) \\ f_i = a_i \sum_{d \mid a_i} g_{i,d}

把 g_{i,d} 改成递推式：

g_{i,d} = \left\{\begin{matrix} g_{i-1,d} + f_i a_i \mu(d) & d \mid a_i \\ g_{i-1,d} & d \nmid a_i \end{matrix}\right.

发现 g_{i,d} 是逐层转移的，可以省去第一维，每次更新完 f_i 之后更新每个 g_d，自然就满足 j<i 的限制。

另外记得预处理每个数的所有因子，不然时间复杂度是 O(n \sqrt n)，由于所有数的因子个数是 O(n \log n) 级别的，所以预处理完总的时间复杂度就是 O(n \log n)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
#define MOD 998244353

ll n, inv[N], a[N], u[N], g[N], f[N];
vector<ll> v[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n; u[1] = f[1] = 1, inv[1] = 1;
    for(int i = 2; i <= n; i ++) 
        inv[i] = (MOD - MOD / i * inv[MOD % i] % MOD) % MOD;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) for(int j = i; j <= n; j += i) v[j].push_back(i);
    for(int i = 1; i <= n; i ++) {
        ll res = inv[i];
        for(auto d : v[i]) if(d != i) res = (res - u[d] + MOD) % MOD;
        u[i] = res;
    }
    for(auto d : v[a[1]]) g[d] = (g[d] + u[d] * f[1] % MOD * a[1] % MOD) % MOD;
    for(int i = 2; i <= n; i ++) {
        for(auto d : v[a[i]]) f[i] = (f[i] + g[d]) % MOD;
        f[i] = f[i] * a[i] % MOD;
        for(auto d : v[a[i]]) g[d] = (g[d] + u[d] * f[i] % MOD * a[i] % MOD) % MOD;
    }
    for(int i = 2; i <= n; i ++) cout << f[i] << "\n";
    return 0;
}