炫酷反演魔术！
莫反会用到的具体性质证明先不写，先写题。
与其说是学习笔记，不如说是简要的题解集合。
不太想贴太多代码啊，翻起来很烦。
P3455 [POI2007]ZAP-Queries
很基础的一道题。令 \(a\le b\)，考虑 \(k=1\) 的情况。
\[\begin{aligned} ans&=\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=1]\\ &=\sum\limits_{i=1}^a\sum\limits_{j=1}^b\varepsilon(\gcd(i,j))\\ &=\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{d|\gcd(i,j)}\mu(d)\\ &=\sum\limits_{d=1}^a\mu(d)\sum\limits_{d|a}\sum\limits_{d|b}\\ &=\sum\limits_{d=1}^a\mu(d)\lfloor\dfrac{a}{d}\rfloor\lfloor\dfrac{b}{d}\rfloor\\ \end{aligned} \]线性筛预处理 \(\mu(n)\) 前缀和，二维整除分块即可。那么，\(k>1\) 呢？直接 \(a\gets\lfloor\dfrac{a}{k}\rfloor\)，\(b\gets\lfloor\dfrac{b}{k}\rfloor\) 即可。
P2522 [HAOI2011]Problem b
容斥以后就跟上面是一样的了。
AcWing221. 龙哥的问题
显然上式等于 \(\sum\limits_{d|n}d\times\varphi(\dfrac{n}{d})\)。因为 \(\varphi(n)\) 是积性函数，所以对于 \(n=\prod\limits_{i=1}^kp_i^{e_i}\)，有上式等于 \(\prod\limits_{i=1}^k\sum\limits_{j=0}^{e_i}p_i^j\times\varphi(p_i^{e_i-j})\)。对于 \(e_i-j>0\)，容易发现 \(p_i^j\times\varphi(p_i^{e_i-j})\) 始终为 \((p_i-1)p_i^{e_i-1}\)。所以上式等于 \(\prod\limits_{i=1}^ke_i(p_i-1)p_i^{e_i-1}+p_i^{e_i}\)。
HDU1695 GCD
相当于求 \(\sum\limits_{i=1}^b\sum\limits_{j=i}^d[\gcd(i,j)=k]\)，在 ZAP-Queries 的基础上减去 \(-[b\ge 1]+\sum\limits_{i=1}^b\varphi(i)\) 即可。
md，有 \(k=0\) 的情况，不特判会 RE。
P1829 [国家集训队]Crash的数字表格 / JZPTAB
令 \(n\le m\)。
\[\begin{aligned} ans&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\text{lcm}(i,j)\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dfrac{ij}{\gcd(i,j)}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j,\gcd(\frac{i}{d},\frac{j}{d})=1}\dfrac{ij}{d}\\ &=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\cdot [\gcd(i,j)=1]\\ &=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\cdot \varepsilon(\gcd(i,j))\\ \end{aligned} \]记 \(f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^mij\cdot \varepsilon(\gcd(i,j))\)，令 \(n\le m\)。
\[\begin{aligned} f(n,m)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^mij\cdot \varepsilon(\gcd(i,j))\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^mij\sum\limits_{d|\gcd(i,j)}\mu(d)\\ &=\sum\limits_{d=1}^n\mu(d)\cdot d^2\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\\ &=\sum\limits_{d=1}^n\mu(d)\cdot d^2\dfrac{(\lfloor\frac{n}{d}\rfloor+1)\lfloor\frac{n}{d}\rfloor}{2}\cdot\dfrac{(\lfloor\frac{m}{d}\rfloor+1)\lfloor\frac{m}{d}\rfloor}{2}\\ \end{aligned} \]\(f(n,m)\) 可以整除分块 \(O(\sqrt{n}+\sqrt{m})\) 求，\(ans=\sum\limits_{d=1}^nd\cdot f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)\) 也可以整除分块 \(O(\sqrt{n}+\sqrt{m})\) 求，总的就是 \(O(n)\)。
算 \(f(n,m)\) 的时候注意因为 \(n,m\le10^7\)，\(\dfrac{(\lfloor\frac{m}{d}\rfloor+1)\lfloor\frac{m}{d}\rfloor}{2}\) 先乘后除不会爆 long long，但如果直接乘上前面那部分再取模就会了，建议三项分别取模再一个个撑起来取模。
SPOJ5971 LCMSUM - LCM Sum
没做出来，看了 oiwiki 之后大受震撼，就当见世面了。
多测，求 \(\sum\limits_{i=1}^n\text{lcm}(i,n)\)。\(n,T\le50000\)。
\[\begin{aligned} ans&=\sum\limits_{i=1}^n\text{lcm}(i,n)\\ &=\sum\limits_{i=1}^{n}\dfrac{in}{\gcd(i,n)}\\ &=n+\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dfrac{in}{\gcd(i,n)}+\dfrac{in}{\gcd(n-i,n)}\\ &=n+\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dfrac{in+(n-i)n}{\gcd(i,n)}\\ &=n+\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dfrac{n^2}{\gcd(i,n)}\\ &=\dfrac{n}{2}+\dfrac{1}{2}\sum\limits_{i=1}^{n}\dfrac{n^2}{\gcd(i,n)}\\ &=\dfrac{n}{2}+\dfrac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{d|i,d|n,\gcd(\frac{i}{d},\frac{n}{d})=1}\dfrac{n^2}{d}\\ &=\dfrac{n}{2}+\dfrac{n^2}{2}\sum\limits_{d|n}\frac{1}{d}\varphi(\frac{n}{d})\\ &=\dfrac{n}{2}+\dfrac{n^2}{2}\sum\limits_{d|n}\frac{d}{n}\varphi(d)\\ &=\dfrac{n}{2}+\dfrac{n}{2}\sum\limits_{d|n}d\varphi(d)\\ \end{aligned} \]令 \(f(n)=\sum\limits_{d|n}d\varphi(d)\)，显然 \(f(n)\) 是积性函数。只要我们能线性筛出 \(f(n)\) 就可以做到 \(O(n+T)\) 了。那么，能做到吗？
如果 \(p\nmid n\)，则 \(f(np)=f(n)f(p)\)；否则，令 \(n=n'p^k,\gcd(n',p)=1\)，考虑 \(f(p^k)\) 的值。\(f(p^k)=\sum\limits_{i=0}^kp^i\varphi(p^i)=p^k\varphi(p^k)+\sum\limits_{i=0}^{k-1}p^i\varphi(p^i)=p^k(p-1)p^{k-1}+f(p^{k-1})\)。则
\[\begin{aligned} &f(np)=f(n')f(p^{k+1})=f(n')((p-1)p^{2k+1}+f(p^k))\\ &f(n)=f(n')f(p^k)=f(n')((p-1)p^{2k-1}+f(p^{k-1}))\\ &f(\frac{n}{p})=f(n')f(p^{k-1})\\ \end{aligned} \]相邻作差得到
\[\begin{aligned} &f(np)-f(n)=f(n')f(p^{k+1})=f(n')(p-1)p^{2k+1}\\ &f(n)-f(\frac{n}{p})=f(n')(p-1)p^{2k-1}\\ \end{aligned} \]故 \(f(np)=f(n)+f(n')(p-1)p^{2k+1}=f(n)+p^2(f(n)-f(\frac{n}{p}))\)。
P3327 [SDOI2015] 约数个数和
先根据 \(d(nm)\) 的性质推一下性质。
\[\begin{aligned} d(nm)&=\sum\limits_{i|n}\sum\limits_{j|m}[\gcd(i,j)=1]\\ &=\sum\limits_{i|n}\sum\limits_{j|m}\varepsilon(\gcd(i,j))\\ &=\sum\limits_{i|n}\sum\limits_{j|m}\sum_{d|\gcd(i,j)}\mu(d)\\ &=\sum_{d=1}^n\mu(d)\sum\limits_{i|n}\sum\limits_{j|m}[d|\gcd(i,j)]\\ &=\sum_{d|n,d|m}\mu(d)\sum\limits_{i|\frac{n}{d}}\sum\limits_{j|\frac{m}{d}}1\\ &=\sum_{d|n,d|m}\mu(d)d(\frac{n}{d})d(\frac{m}{d})\\ \end{aligned} \]代回题目所求式子，得
\[\begin{aligned} ans&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d(ij)\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{d|i,d|j}\mu(d)d(\frac{i}{d})d(\frac{j}{d})\\ &=\sum_{d=1}^n\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}d(i)d(j)\\ &=\sum_{d=1}^n\mu(d)\left(\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}d(i)\right)\left(\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}d(j)\right)\\ \end{aligned} \]可以在 \(O(n)\) 的时间内预处理 \(d(i)\) 及其前缀和。
\[d(np)=\begin{cases}2d(n)&p\nmid n\\2d(n)-d(\frac{n}{p})&p\mid n\end{cases} \]总时间复杂度 \(O(n+T\sqrt{n})\)。
标签：dfrac,lfloor,frac,gcd,limits,乌斯,sum,反演,莫比 From： https://www.cnblogs.com/xx019/p/17504011.html