题解：AT_ndpc2026_l 最小公倍数
manboo
·
·
题解
概述来说，\operatorname{lcm} 可以转化为 \gcd，然后使用莫比乌斯反演。
具体来说，\operatorname{lcm}\left(a,b\right)=\frac{a\cdot b}{\gcd\left(a,b\right)}，则：
\begin{aligned}f_v&=\sum\limits_{k=1}^{v-1}f_k\cdot\operatorname{lcm}\left(A_k,A_v\right)\\&=\sum\limits_{k=1}^{v-1}f_k\cdot\frac{A_k\cdot A_v}{\gcd\left(A_k,A_v\right)}\\&=A_v\cdot\sum\limits_{k=1}^{v-1}f_k\cdot A_k\cdot\frac{1}{\gcd\left(A_k,A_v\right)}\end{aligned}
:::info[积性函数]{open}
若函数 $f\left(n\right)$ 满足 $f\left(1\right)=1$，且对于其定义域内的任意互质的 $x,y\in\mathbb{N}^*$，都有 $f\left(x\cdot y\right)=f\left(x\right)\cdot f\left(y\right)$，则称函数为积性函数。
本文还会用到几个结论：
- 积性函数除以积性函数，得到的还是积性函数。
- 积性函数的狄利克雷卷积还是积性函数。
:::
设 $\phi\left(n\right)=\prod_{p\mid n}\left(1-p\right)$，其中 $p$ 为**质数**，则 $\phi\left(n\right)$ 表示 $n$ 的全体**质因数**的 $1-p$ 的乘积。同时钦定 $\phi\left(1\right)=1$。
显然，它是积性函数，因为 $x$ 与 $y$ 互质时，$x$ 的质因数集合和 $y$ 的质因数集合不相交，且 $x\cdot y$ 的质因数集合是 $x$ 和 $y$ 的质因数集合的并集。
那么，$\frac{\phi\left(n\right)}{n}$ 也是积性函数，因为积性函数除以积性函数还是积性函数。
设 $F_n=\sum\limits_{d\mid n}\frac{\phi\left(d\right)}{d}$ 表示 $n$ 的全体**因子**的 $\frac{\phi\left(n\right)}{n}$ 之和，也是积性函数，因为它是两个积性函数的狄利克雷卷积。
- 当 $n$ 是质数的幂次，也就是存在 $p^a=n$ 且 $p$ 为质数时，$F_n=\frac{1}{n}$，因为：
$$\begin{aligned}F_n&=\sum_{d\mid n}\frac{\phi\left(d\right)}{d}\\&=\sum\limits_{i=0}^{a}\frac{\phi\left(p^i\right)}{p^i}\\&=1+\sum_{i=1}^a\frac{1-p}{p^i}\\&=1+\sum_{i=1}^a\left(\frac{1}{p^i}-\frac{1}{p^{i-1}}\right)\\&=1+\sum_{i=1}^a\frac{1}{p^i}-\sum_{i=0}^{a-1}\frac{1}{p^i}\\&=1+\frac{1}{p^a}-\frac{1}{p^0}\\&=\frac{1}{p^a}\\&=\frac{1}{n}\end{aligned}$$
- 当 $n$ 不是质数的幂次时，也可以通过积性函数的性质推得 $F_n=\frac{1}{n}$。
于是将 $\frac{1}{\gcd(A_k, A_v)}=F_{\gcd(A_k, A_v)}$ 用定义式展开：$f_v=A_v\cdot\sum\limits_{k=1}^{v-1}f_k\cdot A_k\cdot\sum\limits_{d\mid\gcd\left(A_k,A_v\right)}\frac{\phi\left(d\right)}{d}$。
设 $g_d=\sum\limits_{k\in\left[1,v\right),d\mid A_k} f_k\cdot A_k$，交换求和顺序：$f_v=A_v\cdot\sum\limits_{d\mid A_v}\frac{\phi\left(d\right)}{d}\cdot g_d
所以枚举 A_v 的因子 d，累加 \frac{\phi\left(d\right)}{d}\cdot g_d 即可求出 f_v，并将 f_v\times A_v 加入到 g_{d\mid A_v} 中。
根据调和级数，可以证明时间复杂度为 O\left(n\log\left(n\right)\right)。
代码如下：
const int mod=998244353;
inline int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=(ll)res*a%mod;
a=(ll)a*a%mod,b>>=1;
}
return res;
}
const int N=200001;
int n,phi[N],a[N],k[N],f[N],g[N];
vector<int> ys[N];
int main()
{
n=read(),phi[1]=1;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) ys[j].push_back(i); //存储每个数的非1因数
for(int i=2,minp=0;i<=n;i++)
{
minp=ys[i][1]; //取最小因数，此时必然是质因数
if(i/minp%minp==0) phi[i]=phi[i/minp]; //不造成新贡献
else phi[i]=(ll)phi[i/minp]*(1ll-minp+mod)%mod; //造成新贡献1-minp
}
for(int i=1;i<=n;i++) k[i]=(ll)phi[i]*ksm(i,mod-2)%mod; //phi(d)/d
f[1]=1ll;
for(auto j:ys[a[1]]) g[j]=a[1];
for(int i=2;i<=n;i++)
{
for(auto j:ys[a[i]]) f[i]=(f[i]+(ll)g[j]*k[j]%mod)%mod;
f[i]=(ll)f[i]*a[i]%mod;
for(auto j:ys[a[i]]) g[j]=(g[j]+(ll)f[i]*a[i]%mod)%mod;
print(f[i]),putchar('\n');
}
return 0;
}
参考文献：积性函数。