自动搬运

查看原文

来自洛谷，原作者为

	飞雨烟雁 尽管我们走不了最短路，但图仍是连通图，TLE之前，没有一个节点叫失败。

搬运于2025-08-24 22:47:13，当前版本为作者最后更新于2024-05-09 19:42:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

提供一个 $\Theta(n\log \log n)$ 的做法。

---

先把 $\text{lcm}$ 转为 $\gcd$：

$$f(n)=\sum_{1\le i,j,k\le n}[i+j+k=n]\dfrac{i(j,k)}{(i,j,k)} $$

接着我们考虑消去 $i$：

$$\begin{aligned}f(n)&=\sum_{1\le j,k\le n}[j+k\le n-1]\dfrac{(n-j-k)(j,k)}{(n-j-k,j,k)}\\&=\sum_{1\le j,k\le n}[j+k\le n]\dfrac{(n-j-k)(j,k)}{(n,j,k)}\end{aligned} $$

枚举 $d=(j,k)$：

$$\begin{aligned}f(n)&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{1\le j,k\le n}[(j,k)=d][j+k\le n](n-j-k)\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{1\le j,k\le \frac nd}[(j,k)=1]\left[j+k\le \frac nd\right](n-dj-dk)\end{aligned} $$

枚举 $s=j+k$：

$$\begin{aligned}f(n)&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\sum_{1\le j,k\le \frac nd}[(j,k)=1][j+k=s]\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\sum_{j\ge 1}[(j,s-j)=1]\\&=\sum_{d=1}^n\dfrac{d}{(n,d)}\sum_{2\le s\le \frac nd}(n-ds)\varphi(s)\end{aligned} $$

枚举 $t=(n,d)$：

$$\begin{aligned}f(n)&=\sum_{t|n}\sum_{t|d}^n\dfrac{d}{t}[(n,d)=t]\sum_{2\le s\le \frac nd}(n-ds)\varphi(s)\\&=\sum_{t|n}\sum_{d\le \frac nt}d\left[\left(\frac nt,d\right)=1\right]\sum_{2\le s\le \frac n{td}}(n-tds)\varphi(s)\\ &=\sum_{t|n}t\sum_{sd\le \frac nt}[s\ge 2]\left[\left(\frac nt,d\right)=1\right]d\left(\frac nt-ds\right)\varphi(s)\\ \end{aligned}$$

我们把内层求和设为 $g(n)$，即令：

$$g(n)=\sum_{sd\le n}[s\ge 2]\left[\left(n,d\right)=1\right]d\left(n-ds\right)\varphi(s) $$

可以发现我们要求的就是：

$$f(n)=\sum_{t|n}tg\left(\frac nt\right)=n\sum_{t|n}\frac {g(t)}{t} $$

---

下面我们看下如何快速求 $g(n)$。

利用莫反处理 $(n,d)=1$：

$$\begin{aligned}g(n)&=\sum _ {t|n}\mu(t)\sum_{sd\le n}[s\ge 2]\left[t|d\right]d\left(n-ds\right)\varphi(s)\\&=\sum _ {t|n}t^2\mu(t)\sum_{sd\le \frac nt}[s\ge 2]d\left(\frac nt-ds\right)\varphi(s)\end{aligned} $$

我们再次将内层求和设为 $h(n)$，即：

$$h(n)=\sum_{sd\le n}[s\ge 2]d\left(n-ds\right)\varphi(s) $$

则有：

$$g(n)=\sum_{t|n}t^2\mu(t)h\left(\frac nt\right)=n^2\sum_{t|n}\mu\left(\frac nt\right)\frac{h(t)}{t^2} $$

---

下面考虑 $h(n)$ 快速求法。

先剔除 $s\ge 2$ 这个条件：

$$\begin{aligned}h(n)&=\sum_{sd\le n}[s\ge 2]d\left(n-ds\right)\varphi(s)\\&=\sum_{sd\le n}d\left(n-ds\right)\varphi(s)-\sum_{d=1}^nd(n-d)\end{aligned} $$

接着枚举 $k=sd$，并设 $\tau(n)=\sum_{d|n}d\varphi(\frac nd)$。

$$\begin{aligned}h(n)&=\sum_{k=1}^n(n-k)\sum_{d|k}d\varphi\left(\frac kd\right)-\frac{n(n-1)(n+1)}{6}\\&=n\sum_{k=1}^n\tau(k)-\sum_{k=1}^nk\tau(k)-\frac{n(n-1)(n+1)}{6}\\\end{aligned} $$

酱紫就推完啦！

至于 $\tau(n)$，通过简单的推导可知：

$$\tau(pn)=\begin{cases}2p-1&n=1\\\tau(p)\tau(n)&p\nmid n\\ 2p\tau(n)-p^2\tau(n/p)& p\mid n\end{cases} $$

可以线性筛。

---

我们总结一下步骤：

0. 线性递推求逆元；

1. 线性筛出 $\tau(1),\tau(2),\cdots,\tau(n)$ 的值；

2. 求出 $h(1),h(2),\cdots,h(n)$ 的值。

3. 对 $h(n)/n^2$ 做 Dirichlet 差分，得到 $g(1)/1^2,\cdots,g(n)/n^2$；

4. 对 $g(n)/n$ 做 Dirichlet 前缀和，即得 $f(1)/1,\cdots,f(n)/n$。

总时间复杂度是 $\Theta(n\log \log n)$，目前为最优解。

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int Mx = 1e6 + 100, Mod = 998244353;

bool Vis[Mx];
int Tau[Mx], Prime[Mx], tot;
int Inv[Mx];

void Sieve(){
	Tau[1] = 1;
	for(int i = 2; i < Mx; ++i){
		if(!Vis[i]) Prime[++tot] = i, Tau[i] = 2 * i - 1;
		for(int j = 1; j <= tot && Prime[j] * i < Mx; ++j){
			Vis[i * Prime[j]] = true;
			if(i % Prime[j] == 0){
				Tau[i * Prime[j]] = Prime[j] * (2 * Tau[i] - Prime[j] * Tau[i / Prime[j]]);
				break;
			}
			Tau[i * Prime[j]] = Tau[i] * Tau[Prime[j]];
		}
	}
}

void GetInv(){
	Inv[1] = 1;
	for(int i = 2; i < Mx; i++) Inv[i] = -1ll * Inv[Mod % i] * (Mod / i) % Mod;
}

int H[Mx];
int main(){
	Sieve(), GetInv();
	int n; cin >> n;
	int H0 = 0, H1 = 0;
	for(int i = 1; i <= n; ++i){
		H0 = (H0 + Tau[i]) % Mod;
		H1 = (H1 + 1ll * i * Tau[i]) % Mod;
		H[i] = (H0 - 1ll * Inv[i] * H1 - (i - 1ll) * (i + 1ll) % Mod * Inv[6]) % Mod * Inv[i] % Mod;
	}
	for(int i = 1; Prime[i] <= n; ++i){
		for(int j = n / Prime[i]; j; --j){
			H[j * Prime[i]] = (H[j * Prime[i]] - H[j]) % Mod;
		}
	}
	for(int i = 1; i <= n; ++i) H[i] = 1ll * i * H[i] % Mod;
	for(int i = 1; Prime[i] <= n; ++i){
		for(int j = 1; j * Prime[i] <= n; ++j){
			H[j * Prime[i]] = (H[j * Prime[i]] + H[j]) % Mod;
		}
	}
	for(int i = 1; i <= n; ++i){
		int Ans = 1ll * H[i] * i % Mod;
		if(Ans < 0) Ans += Mod;
		printf("%d ", Ans);
	}
	return 0;
}