炫酷反演魔术！
莫反会用到的具体性质证明先不写，先写题。
与其说是学习笔记，不如说是简要的题解集合。
不太想贴太多代码啊，翻起来很烦。
很基础的一道题。令 \(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\) 即可。
容斥以后就跟上面是一样的了。
显然上式等于 \(\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}\)。
相当于求 \(\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。
令 \(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，但如果直接乘上前面那部分再取模就会了，建议三项分别取模再一个个撑起来取模。
没做出来，看了 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}))\)。
先根据 \(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})\)。