莫比乌斯反演

今日又一次学习了莫比乌斯反演，终于理解了。
问题：求有多少数对\((x,y)\)，\(1\le x\le n\)，\(1\le y \le m\)，\(\gcd(x,y)=1\)。
莫比乌斯函数：
\(\mu(d) = \left\{\begin{matrix} 1 & d=1\\ (-1)^k & d=\prod _{i=1}^{k} p_i(p_i\ne p_j)\\ 0 & else\end{matrix}\right.\)
这个函数是一个积性函数，即\(\mu(x\times y)=\mu(x)\times \mu(y)\)，对于\(\gcd(x,y)=1\)。
这样就会得到
\(\sum_{d\mid n}\mu(d)=\left\{\begin{matrix} 1 & n=1\\0 & n\ne 1 \end{matrix}\right.\)
这里我是这样理解，首先对于\(1\)和质数来说，这个式子是显然的，然后对于其余的\(x\)，设\(f(x)=\sum_{d\mid x} \mu(d)\)，根据数学归纳法，假定\(f(x)=0\)，且存在一个质数\(y\)。
有两种情况：
1.\(y\mid x\)，那么\(x\times y\)的因数中不是\(x\)的因数的一定可以被\(y^2\)整除，即\(f(x\times y)=f(x)+0=0\)。
2.\(\gcd(x,y)=1\)，对于\(x\)的任意一个因数\(w\)，\(x\times y\)中一定存在一个因数\(w\)和一个因数\(w\times y\)，且\(\gcd(w,y)=1\)，\(\mu(w\times y)=\mu(w)\times \mu(y)\)，即\(\mu(w\times y)+\mu(w)=0\)，\(f(x\times y)=0\)。
最后解决这个问题
\(\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1]=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)}\mu(d)=\sum_{d=1}^{n}\mu(d)\times \left \lfloor \frac{n}{d} \right \rfloor \times \left \lfloor \frac{m}{d} \right \rfloor\)
使用数论分块就可以在\(\Theta (\sqrt{n} +\sqrt{m} )\)的复杂度下通过。