莫比乌斯函数重要性质
\([n = 1] = \sum \limits _{d | n} \mu(d)\)
应用 ： \(\gcd(a, b) = 1 \Leftrightarrow \sum \limits _{d | \gcd(a, b)} \mu(d)\)
P3327 [SDOI2015] 约数个数和
首先有：
\[d(ij) = \sum_{a | i} \sum_{b | j} [\gcd(a, b) = 1] \]
证明参考题解 1，很神秘的构造方案。
然后推式子：
\[\begin{aligned} \sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} d(ij) &= \sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} \sum_{a | i} \sum_{b | j} [\gcd(a, b) = 1]\\ &= \sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} \sum_{a | i} \sum_{b | j} \sum_{d | \gcd(a, b)} \mu(d)\\ &= \sum_{a = 1} ^ {n} \sum_{b = 1} ^ {m} \left \lfloor \dfrac{n}{a} \right \rfloor \left \lfloor \dfrac{m}{b} \right \rfloor \sum_{d | \gcd(a, b)} \mu(d)\\ &= \sum_{d = 1} ^ {\min(n, m)} \mu(d) \sum_{a = 1} ^ {\left \lfloor \frac{n}{d} \right \rfloor} \sum_{b = 1} ^ {\left \lfloor \frac{m}{d} \right \rfloor} \left \lfloor \dfrac{n}{ad} \right \rfloor \left \lfloor \dfrac{m}{bd} \right \rfloor \\ &= \sum_{d = 1} ^ {\min(n, m)} \mu(d) \sum_{a = 1} ^ {\left \lfloor \frac{n}{d} \right \rfloor} \left \lfloor \dfrac{n}{ad} \right \rfloor \sum_{b = 1} ^ {\left \lfloor \frac{m}{d} \right \rfloor} \left \lfloor \dfrac{m}{bd} \right \rfloor \end{aligned} \]定义 \(f(n) = \sum_{i = 1} ^ {n} \left \lfloor \frac{n}{i} \right \rfloor\) 。整除分块预处理 \(f\)，最终得到
\[ans = \sum_{d = 1} ^ {\min(n, m)} \mu(d) f(\left \lfloor \frac{n}{d} \right \rfloor) f(\left \lfloor \frac{m}{d} \right \rfloor) \]每次询问时再做一次整除分块，最终复杂度为 \(O(n \sqrt n + T \sqrt n)\)。
P1829 [国家集训队] Crash的数字表格 / JZPTAB
简单题，每一步都很自然，直接放最终结论。
设 \(f(n, m) = \sum \limits _{i = 1} ^ {\min(n, m)} i ^ 2 \mu(i) s(\left \lfloor \frac{n}{i} \right \rfloor) s(\left \lfloor \frac{m}{i} \right \rfloor)\)，其中 \(s(n) = \frac{n \times (n + 1)}{2}\)，那么最终答案为 \(\sum \limits _{i = 1} ^ {\min(n, m)} i \cdot f(\left \lfloor \frac{n}{i} \right \rfloor, \left \lfloor \frac{m}{i} \right \rfloor)\)，直接套两层整除分块即可。
标签：lfloor,right,frac,sum,rfloor,莫反乱,left From： https://www.cnblogs.com/harqwq/p/17930075.html