题目大意：
设\(d(x)\)为\(x\)的约数个数，给定\(n,m\)，求
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)\]
首先我们需要知道一个神仙定理：
\[d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)==1]\]
证明：
假设\(ij\)中存在因子\(p^k\)，且\(i\)中\(p\)的最高次因子为\(p^{k_1}\),且\(j\)中\(p\)的最高次因子为\(p^{k_2}\),那么：
当 \(k<=k_1\) 我们可以认为在\(i\)中选择了\(k\)个
当 \(k>k_1\) 我们可以认为在&i&总选择了\(k_1\)个，并且在\(j\)中选择了\(k-k_1\)个
这样就可以构成一个任意一个质因子的任意次幂的映射，这个映射成立的前提是\([gcd(i,j)==1]\)
就这样证完啦_(:з」∠)_
所以根据神仙定理
\[ret=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)==1]\]
把枚举因子提前，枚举倍数
\[ret=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\frac{n}{x}\rfloor \lfloor\frac{m}{y}\rfloor [gcd(x,y)==1]\]
\(x,y\)看着不顺眼，改成\(i,j\)吧\(qwq\)
\[ret=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\lfloor\frac{n}{i}\rfloor \lfloor\frac{m}{j}\rfloor [gcd(i,j)==1]\]
按照\(YY\)的\(GCD\)的套路，设
\[f(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\lfloor\frac{n}{i}\rfloor \lfloor\frac{m}{j}\rfloor [gcd(i,j)==x]\]
\[g(x)=\sum\limits_{x|d}f(d)\]
则
\[g(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\lfloor\frac{n}{i}\rfloor \lfloor\frac{m}{j}\rfloor [x|gcd(i,j)]\]
将\(x\)提出来，消除\(gcd\)的影响
\[g(x)=\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{n}{ix}\rfloor \lfloor\frac{m}{jx}\rfloor\]
根据莫比乌斯反演第二形式，有
\[f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})*g(d)\]
由题意得
\[ret=f(1)=\sum\limits_{1|d}\mu(\frac{d}{1})*g(d)=\sum\limits_{d=1}^{min(n,m)}\mu(d)g(d)\]
将\(g(i)\)展开得到
\[ret=\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{di}\rfloor\lfloor\frac{m}{dj}\rfloor\]
发现\(\lfloor\frac{n}{di}\rfloor\)和\(j\)没有关系，把它提前
\[ret=\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{di}\rfloor\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dj}\rfloor\]
到此，我们可以设
\[s(n)=\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\]
这个\(s\)可以\(O(n\sqrt{n})\)预处理
\[ret=\sum\limits_{d=1}^{min(n,m)}\mu(d)s(\lfloor\frac{n}{d}\rfloor)s(\lfloor\frac{m}{d}\rfloor)\]
然后直接除法分块就好了，复杂度\(O(n\sqrt{n}+T\sqrt{n})\)
洛谷P3327 [SDOI2015]约数个数和（莫比乌斯反演）
原文：https://www.cnblogs.com/knife-rose/p/12016959.html