$\epsilon = \mu * 1$，证明：二项式定理$(1 - 1)^2 = 0$。

$\operatorname{id} = \varphi * 1$，证明：真分数约分。

$\varphi= \mu * \operatorname{id}$，证明：上面式子左右卷$\mu$。

求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$$ 先枚举$d = \gcd(i,j)$，再套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\sum_{p|\gcd(i,j)}\mu(p)$$ 再枚举$p$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{dp} \right\rfloor}1$$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\frac{\left\lfloor \frac{n}{dp} \right\rfloor(\left\lfloor \frac{n}{dp} \right\rfloor + 1)\left\lfloor \frac{m}{dp} \right\rfloor(\left\lfloor \frac{m}{dp} \right\rfloor + 1)}{4}$$ 设$T=dp$，枚举$T$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\sum_{d|T}d\mu(\frac{T}{d})$$ 套用$\varphi= \mu * \operatorname{id}$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\varphi(T)$$ 求出欧拉函数前缀和，直接整除分块即可。

上述过程中最为关键的是设$T=dp$，枚举$T$这一步。该操作可以概括为如下等式：$$\sum_{d=1}^{n}f(d)\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}g(p)h(dp)=\sum_{T=1}^{n}h(T)\sum_{d|T}f(d)g(\frac{T}{d})$$设$F(n)=\sum_{d|n}f(d)g(\frac{n}{d})$，则原式可化为$$\sum_{T=1}^{n}h(T)F(T)$$如果两个函数一个可以整除分块，另一个可以在合理时限内求出前缀和，那么就可以以较低时间复杂度求出答案。

结论：$$\sum_{i=1}^ni[\gcd(i,n)=1]=\frac{n\varphi(n)+[n==1]}{2}$$ 证明如下：