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)\) 可以通过狄利克雷后缀和处理。