1、来源 InfOJ54
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)\varphi(ij)\mu(ij),\qquad n,m\le 5\times10^7 \]通过莫比乌斯函数 \(\mu\) 的性质可知，如果 \(\gcd(i,j)\not=1\)，\(\mu(ij)\) 是一定等于 \(0\) 的。
又因为 \(\varphi\) 与 \(\mu\) 都为积性函数，那么可得
\[\begin{align*} &\quad\ \sum_{i = 1}^{n}\sum_{j = 1}^{m}\varphi(i)\varphi(j)\mu(i)\mu(j)\left[\gcd(i,j) = 1\right]\\ & = \sum_{i = 1}^{n}\varphi(i)\mu(i)\sum_{j = 1}^{m}\varphi(j)\mu(j)\left[\gcd(i,j) = 1\right]\\ & = \sum_{i = 1}^{n}\varphi(i)\mu(i)\sum_{j = 1}^{m}\varphi(j)\mu(j)\sum_{d\mid\gcd(i,j)}\mu(d)\\ & = \sum_{i = 1}^{n}\varphi(i)\mu(i)\sum_{j = 1}^{m}\varphi(j)\mu(j)\sum_{d = 1}^{\min(n,m)}[d\mid i][d\mid j]\mu(d)\\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{d\mid i}^{n}\varphi(i)\mu(i)\sum_{d\mid j}^{m}\varphi(j)\mu(j)\\ \end{align*} \]其中 \(\mu\) 与 \(\varphi\) 可以通过线性筛处理，而 \(f(d)=\sum_{d\mid i}^{n}\varphi(i)\mu(i)\) 可以通过狄利克雷后缀和处理。
标签：gcd,sum,mid,varphi,mu,ij,简简单单,式子 From： https://www.cnblogs.com/Cnghit/p/17674022.html