本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 21:57:32

这次又没能自己做出来，卡死在了线性筛那一步，参照的这篇题解。

$f(n)$ 代表 $n$ 的质因子的最大幂指数。

假设 $a \le b$。

求 $\sum\limits_{i=1}^a\sum\limits_{j=1}^b f(\gcd(i,j))$。

转化：
$\sum\limits_{d=1}^a\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} [(i,j)=1]f((i,j))$
$= \sum\limits_{d=1}^a f(d)\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} \sum\limits_{k|(i,j)}\mu(k) $
$=\sum\limits_{d=1}^a f(d)\sum\limits_{k=1}^{\lfloor \frac{a}{d}\rfloor}\mu(k) \lfloor\frac{a}{dk}\rfloor\lfloor\frac{b}{dk}\rfloor$。

为了方便求解，可以将其转化为 Dirchlet 卷积的形式，令 $T =dk$。

原式转化为：$\sum\limits_{T=1}^a \sum\limits_{d|T}f(d)\mu(\frac{T}{d})\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor$。

设 $g(i) = \sum\limits_{d|i}f(d)\mu(\frac{i}{d})$，现在只需要找到一个方法快速求出 $g(1),g(2),\cdots,g(a)$，就可以使用整除分块解决本题。

假设线性筛当前筛到了 $x = a_1^{p_1}\cdot a_2^{p_2}\cdot \cdots \cdot a_kp^k$，$\frac{x}{d} = a_1^{q_1}\cdot a_2^{q_2}\cdot \cdots \cdot a_k^{q_k}$。

此时的背景是正在计算 $f(d)\mu(\frac{T}{d})$。

需要注意的是，由于莫比乌斯函数的性质，值若不为 $0$，那么 $q_i$ 只能为 $0$ 或 $1$。

考虑一件事情，如果 $x$ 的某个质数的幂次不等于 $f(x)$，那么这个质数归类于 $d$ 还是 $f(d)$ 不会导致 $f(d)$ 的变化，但是 $\mu(\frac{T}{d})$ 的值却会因此翻转，导致答案变为 $0$。

下面考虑 $x$ 的每个质因数的幂次相同的情况。

对于 "普通" 的情况，还是按照上一种。

特殊情况，就是 $1 \le \forall i \le k, q_i=p_i-1$，不难注意到这种情况不会被抵消掉。

经过上述分类讨论发现，只有这种特殊情况不会被抵消掉，得出结论：

1. 若 $x$ 的质因子的幂次不全相同，那么 $g(x)=0$。
2. 否则，令 $m$ 为 $x$ 的质因子个数，$g(x)=(-1)^{m+1}$。

然后就可以快乐的线性筛了。