我从不怕摔倒
拼命向前跑
把每一天过好
和大家拥抱----乐正绫《万圣街》
T1. P5572 [CmdOI2019] 简单的数论题
和毒瘤之神的考验类似的毒瘤题。
首先先化简原式：
\[\begin{array}{l}\sum^n_{i = 1} \sum^m_{j = 1} \varphi(\dfrac{{\rm lcm}(i,j)}{\gcd(i,j)}) = \sum^n_{i = 1}\sum^m_{j = 1} \varphi(\dfrac{i \times j}{\gcd(i,j)^2})\\=\sum^n_{d = 1}\sum^{n}_{i = 1}\sum^m_{j = 1} \varphi(\dfrac{i \times j}{d^2})[\gcd(i,j) == d]\\=\sum^n_{d = 1}\sum^{\lfloor \frac{n}{d} \rfloor}_{i = 1}\sum^{\lfloor \frac{m}{d} \rfloor}_{j = 1} \varphi(i \times j)[\gcd(i,j) == 1]\\=\sum^n_{d = 1}\sum^{\lfloor \frac{n}{d} \rfloor}_{i = 1}\sum^{\lfloor \frac{m}{d} \rfloor}_{j = 1} \varphi(i) \times \varphi(j)[\gcd(i,j) == 1]\\=\sum^n_{d = 1}\sum^{\lfloor \frac{n}{d} \rfloor}_{i = 1}\sum^{\lfloor \frac{m}{d} \rfloor}_{j = 1} \varphi(i) \times \varphi(j) \sum_{p \mid \gcd(i,j)} \mu(p)\\=\sum^n_{d = 1}\sum^{\lfloor \frac{n}{d} \rfloor}_{p = 1} \mu(p) \sum^{\lfloor \frac{n}{d} \rfloor}_{i = 1} \sum^{\lfloor \frac{m}{d} \rfloor}_{j=1} \mu(i) \mu(j) [p \mid i] [p \mid j] \\=\sum^n_{d = 1}\sum^{\lfloor \frac{d}{n} \rfloor}_{p = 1} \mu(p) \sum^{\lfloor \frac{n}{pd} \rfloor}_{i = 1} \varphi(ip) \sum^{\lfloor \frac{m}{pd} \rfloor}_{j = 1} \varphi(jp)\\=\sum^n_{T = 1} \sum_{p | T} \mu(p) \sum^{\lfloor \frac{n}{T} \rfloor}_{i = 1} \mu(ip) \sum^{\lfloor \frac{m}{T} \rfloor}_{j = 1} \varphi(jp)\end{array} \]然后我们设 \(G(x,y) = \sum^x_{i = 1} \varphi(iy)\)。那么原式子就变为 \(\sum_{T = 1}^n \sum_{p | T} \mu(p) G(\lfloor \frac{n}{T} \rfloor,p) G(\lfloor \frac{m}{T} \rfloor,p)\)。
然后我们定义 \(H(x,y,z) = \sum_{T = 1}^z \sum_{p | T} \mu(p) G(x,p) G(y,p)\)。
接着我们就可以用毒瘤之神的考验的套路了。用根号分支来求 \(H\)，具体的我们设置一个阈值 \(B\)，将所有 \(\le B\) 的 \(H\) 都提前预处理出来，然后对于 \(\ge B\) 的部分，我们可以在查询时利用整除分块计算。
标签：lfloor,frac,2024.7,过好,摔倒,rfloor,mu,varphi,sum From： https://www.cnblogs.com/Carousel/p/18316461