给定 $n,m,k$ ，计算
$$
\sum _ {i=1}^n\sum _ {j=1}^m {\gcd(i,j)}^k
$$
对 $1000000007$ 取模的结果
链接
题解
我们来来来推推推式子吧qwq
$$
\sum _ {i=1}^n\sum _ {j=1}^m {\gcd(i,j)}^k
$$
不妨令 $n<m$ ，枚举 $\gcd(i,j) = d$ ：
$$
S = \sum _ {d=1}^{n} d^k \sum _ {i=1}^{\lfloor\frac{n}{d}\rfloor}\sum _ {i=1}^{\lfloor\frac{m}{d}\rfloor} [(i,j)=1]\
= \sum _ {d=1}^{n} d^k \sum _ {i=1}^{\lfloor\frac{n}{d}\rfloor}\sum _ {i=1}^{\lfloor\frac{m}{d}\rfloor} \sum _ {t | \gcd(i,j)} \mu(t)\
= \sum _ {d=1}^{n} d^k \sum _ {t = 1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)\sum _ {i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum _ {i=1}^{\lfloor\frac{m}{dt}\rfloor} 1\
= \sum _ {d=1}^{n} d^k \sum _ {t = 1}^{\lfloor\frac{n}{d}\rfloor} \mu(t) \lfloor\frac{n}{dt}\rfloor \lfloor\frac{m}{dt}\rfloor\
$$
令 $dt = T$ ，我们有：
$$
S = \sum _ {T=1}^{n} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor\sum _ {d|T}d^k\mu(\frac{T}{d})
$$
我们令 $g(T) = \sum _ {d|T}d^k\mu(\frac{T}{d})$，原式变为：
$$
S = \sum _ {T=1}^{n} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor g(T)
$$
很明显这个可以整除分块，很明显 $g$ 是一个积性函数，所以我们考虑如何算出 $g$ 的前缀和。
发现 $n,m$ 的范围比较小，可以考虑用线性筛解决这个问题。
线性筛的本质是不断加入最小质因子，我们考虑一个质数的
$$
g(P^t) = \sum _ {i=0}^t f(P^i) \mu (P^{t-i})
$$
凡是有平方因子的数都是的莫比乌斯函数值都是 $0$ ，所以这个式子化成：
$$
g(P^t) = \mu(1) f(P^t) + \mu(P)f(P^{t-1})\
= f(P^t) - f(P^{t-1})
= P^{kt} - P^{k(t-1)}
= P^{k(t-1)}(P^{k}-1)
$$
可以注意到如果没有 $P$ 这个质因子，答案就是直接乘上 $P^k-1$ ，如果有就乘上 $P^k$ 即可。
这大概也是线性筛筛未知积性函数的套路：算出来 $g(P^t)$ 并观察这个东西的性质，当然也可以记录最小质因子的大小。
时间复杂度： $O(n + T \sqrt n)$ 。
代码
| |
