题解：AT_ndpc2026_l 最小公倍数

· · 题解

更好的阅读体验

一个非常简单的 O(n \sqrt n) 做法。

假设 f_i 表示 1 \to i 的方案数。

\begin{align} f_i &= \sum_{j=1}^{i-1} f_j \cdot \operatorname{lcm}(a_i, a_j) \nonumber \\ &= a_i \sum_{j=1}^{i-1} \frac{f_j \cdot a_j}{\gcd(a_i, a_j)} \nonumber \\ &= a_i \sum_{g} \frac{1}{g} \sum_{j=1}^{i-1} [\gcd(a_i, a_j) = g] f_j \cdot a_j \nonumber \\ &= a_i \sum_{g} \frac{1}{g} \sum_{j=1}^{i-1} \left[\gcd\left(\frac{a_i}{g}, \frac{a_j}{g}\right) = 1 \right] f_j \cdot a_j \nonumber \\ &= a_i \sum_g \frac{1}{g} \sum_{j=1}^{i-1} \left(\sum_d [dg \mid a_i][dg \mid a_j] \mu(d)\right) f_j \cdot a_j \nonumber \\ &= a_i \sum_g \frac{1}{g} \sum_d [dg \mid a_i] \mu(d) \sum_{j=1}^{i-1}[dg \mid a_j] f_j \cdot a_j \nonumber \\ &=a_i \sum_s [s \mid a_i] \left(\sum_{j=1}^{i-1}[s \mid a_j] f_j \cdot a_j\right) \left(\sum_{g} [g \mid s] \frac{1}{g} \cdot \mu \left(\frac{s}{g}\right)\right) \nonumber \end{align}

我们对于每个 s，分别预处理 \sum\limits_{g} [g \mid s] \frac{1}{g} \cdot \mu \left(\frac{s}{g}\right) 和 \sum\limits_{j=1}^{i-1}[s \mid a_j] f_j \cdot a_j 两项即可做到 O(n \sqrt n) 的复杂度。

#include<bits/stdc++.h>
#define endl '\n'
#define N 200006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
int n,a[N],f[N],inv[N],coef[N],sum[N];
int mu[N],vis[N],tot,prime[N];
int qpow(int x,int y=MOD-2)
{
    int ret=1;
    for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
    return ret;
}
vector<int> get(int x)
{
    vector<int> ret;
    for(int i=1;i*i<=x;i++)if(x%i==0)
    {
        ret.push_back(i);
        if(i*i!=x)ret.push_back(x/i);
    }
    return ret;
}
void sieve()
{
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])prime[++tot]=i,mu[i]=MOD-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) {mu[i*prime[j]]=0; break;}
            mu[i*prime[j]]=(MOD-mu[i])%MOD;
        }
    }
}
void update(int i)
{
    vector<int> d=get(a[i]);
    for(int j:d)add(sum[j],1ll*f[i]*a[i]%MOD);
}
main()
{
    scanf("%d",&n),sieve();
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<N;i++)
    {
        inv[i]=qpow(i);
        vector<int> d=get(i);
        for(int j:d)add(coef[i],1ll*inv[j]*mu[i/j]%MOD);
    }
    f[1]=1,update(1);
    for(int i=2;i<=n;i++)
    {
        vector<int> d=get(a[i]);
        for(int j:d)add(f[i],1ll*sum[j]*coef[j]%MOD);
        f[i]=1ll*f[i]*a[i]%MOD;
        update(i),printf("%d\n",f[i]);
    }
    return 0;
}