\(\sigma (xy)\) 相关
结论：
-
\(\sigma_0(xy) = \sum\limits_{i|x} \sum\limits_{j|y} [\gcd(i, j) = 1]\)
-
\(\sigma_1(xy) = \sum\limits_{i|x} \sum\limits_{j|y} [\gcd(i, j) = 1] \frac {xj} i\)
-
\(\sigma_k(xy) = \sum\limits_{i|x} \sum\limits_{j|y} [\gcd(i, j) = 1] (\frac {xj} i) ^ k\)
也就是说，对于所有 \(\gcd(i, j) = 1\)，我们枚举 \(\frac {xj} i\) 就相当于是枚举约数。
可以这样看待双射：对于一个质因子 \(p\)，设其在 \(x, y\) 中的次数分别为 \(a, b\)。我们枚举约数时，优先填满 \(x\) 中 \(a\) 次，再填 \(y\) 中 \(b\) 次。用 \(i\) 表示 \(x\) 中未填的次数，用 \(j\) 表示 \(y\) 中已填的次数，显然 \(i, j\) 两者中至少一个次数为 \(0\)，即相当于 \(\gcd(i, j) = 1\)。由此，进而推出枚举的约数为 \(\frac {xj} i\)。
Luogu8570 [JRKSJ R6] 牵连的世界
\[ \begin{aligned}
\sum\limits_{x = 1} ^ n \sum\limits_{y = 1} ^ m \sigma_0(xy) \varphi(xy) &= \sum\limits_{x = 1} ^ n \sum\limits_{y = 1} ^ m \frac {\varphi(x) \varphi(y) \gcd(x, y)} {\varphi(\gcd(x, y))} \sum\limits_{i | x} \sum\limits_{j | y} [\gcd(i, j) = 1] \frac {xj} i \\
&= \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{x = 1} ^ {\lfloor \frac nd \rfloor} \sum\limits_{y = 1} ^ {\lfloor \frac md \rfloor} \frac {\varphi(dx) \varphi(dy) \gcd(x, y) d} {\varphi(\gcd(x, y) d)} \cdot \sigma_0(x) \sigma_0(y) \\
&= \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{t = 1} ^ {\lfloor \frac {\min(n, m)} d \rfloor} \sum\limits_{k = 1} ^ {\lfloor \frac{\min(n, m)} {dt} \rfloor} \mu(k) \sum\limits_{x = 1} ^ {\lfloor \frac n {dtk} \rfloor} \sum\limits_{y = 1} ^ {\lfloor \frac m {dtk} \rfloor} \frac {\varphi(dtkx) \varphi(dtky) dt} {\varphi(dt)} \cdot \sigma_0(tkx) \sigma_0(tky) \\
&= \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{t = 1} ^ {\lfloor \frac {\min(n, m)} d \rfloor} \frac {dt} {\varphi(dt)} \sum\limits_{k = 1} ^ {\lfloor \frac{\min(n, m)} {dt} \rfloor} \mu(k) \left (\sum\limits_{x = 1} ^ {\lfloor \frac n {dtk} \rfloor} \varphi(dtkx) \sigma_0(tkx) \right) \left (\sum\limits_{y = 1} ^ {\lfloor \frac m {dtk} \rfloor} \varphi(dtky) \sigma_0(tky) \right) \\
&= \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{s = 1} ^ {\lfloor \frac {\min(n, m)} d \rfloor} \left (\sum\limits_{x = 1} ^ {\lfloor \frac n {ds} \rfloor} \varphi(dsx) \sigma_0(sx) \right) \left (\sum\limits_{y = 1} ^ {\lfloor \frac m {ds} \rfloor} \varphi(dsy) \sigma_0(sy) \right) \left( \sum\limits_{t | s} \frac {dt} {\varphi(dt)} \mu(\frac st) \right)\end {aligned}\]
即可做到 \(\mathcal O(n\log ^ 2n)\)。
平衡思想
Luogu4240 毒瘤之神的考验
不妨假定 \(n\le m\)。
\[ \begin {aligned}
\sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij) &= \sum_{i = 1} ^ n \sum_{j = 1} ^ m \frac {\varphi(i) \varphi(j) \gcd(i, j)} {\varphi(\gcd(i, j))} \\
&= \sum_{d = 1} ^ n \frac d {\varphi(d)} \sum_{t = 1} ^ {\lfloor \frac nd \rfloor} \mu(t) \left(\sum\limits_{i = 1} ^ {\lfloor \frac n {dt} \rfloor} \varphi(dti) \right) \left(\sum\limits_{j = 1} ^ {\lfloor \frac m {dt} \rfloor} \varphi(dtj) \right) \\
&= \sum_{T = 1} ^ n \left( \sum_{d | T} \frac d {\varphi(d)} \cdot \mu(\frac Td) \right) \left(\sum\limits_{i = 1} ^ {\lfloor \frac nT \rfloor} \varphi(Ti) \right) \left(\sum\limits_{j = 1} ^ {\lfloor \frac mT \rfloor} \varphi(Tj) \right)
\end {aligned} \]
记 \(F(k, n) = \sum\limits_{i = 1} ^ n \varphi(ki)\)，记 \(h(n) = \sum_{d | n} \dfrac d {\varphi(d)} \cdot \mu(\dfrac nd)\)，则原式化为
\[\sum_{T = 1} ^ n h(T) F(T, \lfloor \frac nT \rfloor) F(T, \lfloor \frac mT \rfloor)
\]
这和简单的数论分块解法不同，因为 \(\lfloor \frac nT \rfloor\) 和 \(\lfloor \frac mT \rfloor\) 两部分的计算并不独立，换言之，不能将两部分的区间和直接相乘，而是应该对位相乘求和。
记 \(G(k, a, b) = \sum\limits_{i = 1} ^ k h(i) F(i, a) F(i, b)\)，则每次询问数论分块即可。
但是 \(G\) 预处理的位置数达到 \(\mathcal O(n ^ 3)\) 不能接受，考虑设置一个阈值 \(B\)，预处理出 \(G(n, 1\sim B, 1\sim B)\) 的值。
每次询问时，对于 \(T\le \lfloor \dfrac m {B + 1} \rfloor\) 直接枚举求解。剩下的 \(T\) 满足 \(\lfloor \frac mT \rfloor \le B\)，数论分块后利用 \(G\) 求解。
时间复杂度 \(\mathcal O(nB ^ 2 + q(\sqrt n + \dfrac nB))\)，取 \(B = \sqrt [3] q\) 得 \(\mathcal O(nq ^ {\frac 23} + n ^ {\frac 12}q)\)。
Luogu13645 Totient with Divisors
假定 \(n\le m\)。
\[ \begin {aligned}
\sum_{x = 1} ^ n \sum_{y = 1} ^ m \varphi(x) \varphi(y) \sigma(xy) &= \sum_{x = 1} ^ n \varphi(x) \sum_{y = 1} ^ m \varphi(y) \sum_{i | x} \sum_{j | y} [\gcd(i, j) = 1] \frac {xj} i \\
&= \sum_{d = 1} ^ n \mu(d) \sum_{i = 1} ^ {\lfloor \frac nd \rfloor} \sum_{j = 1} ^ {\lfloor \frac md \rfloor} \sum_{x = 1} ^ {\lfloor \frac n {di} \rfloor} \varphi(dix) \sum_{y = 1} ^ {\lfloor \frac m {dj} \rfloor} \varphi(djy) \frac {dix \cdot dj} {di} \\
&= \sum_{d = 1} ^ n d \mu(d) \left(\sum_{i = 1} ^ {\lfloor \frac nd \rfloor} \sum_{x = 1} ^ {\lfloor \frac n {di} \rfloor} \varphi(dix)x \right) \left(\sum_{j = 1} ^ {\lfloor \frac md \rfloor} \sum_{y = 1} ^ {\lfloor \frac m {dj} \rfloor} \varphi(djy)j \right)
\end {aligned}\]
注意到两个括号内得式子形式相同，记 \(F(k, n) = \sum_{i = 1} ^ n \sum_{j = 1} ^ {\lfloor \frac ni \rfloor} \varphi(kij) j\)。则
\[ \begin {aligned}
F(k, n) &= \sum_{ij\le n} \varphi(kij) j \\
&= \sum_{ij \le n - 1} \varphi(kij) j + \sum_{i | n} \varphi(kn) i \\
&= F(k, n - 1) + \varphi(kn) \sigma(k)
\end {aligned} \]
即可递推求解 \(F(k, n)\)。
然后同毒瘤之神的考验。
)
