核心公式

$$n=\sum\limits_{d|n}\phi(d)$$

其在狄利克雷卷积中表示为 $\phi*1=Id$
证明在这里 (opens new window)

反演思想

主要是替换上面这个公式中的 $n$
将一个数学柿子进行转化,从而降低复杂度

利用

化简 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)$

$$\begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|(i,j)}\phi(d)\\ =&\sum\limits_{d=1}^{min(n,m)}\phi(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m[d|i\wedge d|j]\\ =&\sum\limits_{d=1}^{min(n,m)}\phi(d)\left\lfloor\frac nd\right\rfloor\left\lfloor\frac md\right\rfloor \end{aligned}$$

例题

洛谷P1447_能量采集
题目地址 (opens new window)
题解地址 (opens new window)