引入
你遇到了一道数论题：
求 \(S=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)\) 的值，对 \(19260817\) 取膜，\(1\le n\le m\le 10^5\)
“这不是莫比乌斯反演裸题吗？”
\(\begin{aligned} S&=\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\\ &=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\ &=\sum_{d=1}^nd\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1]\\ &=\sum_{d=1}^nd\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{t|\gcd(i,j)}\mu(t)\\ &=\sum_{d=1}^nd\sum_{t=1}^{n/d}\mu(t)\sum_{i=1}^{n/d}[t|i]\sum_{j=1}^{m/d}[t|j]\\ &=\sum_{d=1}^nd\sum_{t=1}^{n/d}\mu(t)\left\lfloor\dfrac{n}{dt}\right\rfloor\left\lfloor\dfrac{m}{dt}\right\rfloor \end{aligned}\)
令 \(T=dt\)
\(\begin{aligned} S&=\sum_{d=1}^nd\sum_{t=1}^{n/d}\mu(t)\left\lfloor\dfrac{n}{dt}\right\rfloor\left\lfloor\dfrac{m}{dt}\right\rfloor\\ &=\sum_{T=1}^n\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\sum_{t\mid T}\mu(t)(T/t)\\ &=\sum_{T=1}^n\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\varphi(T) \end{aligned}\)
至此可以 \(O(n)\) 计算
你有一个朋友，然后你看到了他的做法：
\(\begin{aligned} S&=\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\ &=\sum_{d=1}^{n}\varphi(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned}\)
其中用到了欧拉函数的一条性质：\(\sum\limits_{d\mid n}\varphi(d)=n\)
你看不懂，但大受震撼
朋友告诉你，运用这条性质推式子的过程被称为欧拉反演
欧拉反演
这东西的核心只有上面那一条性质，适用范围也比较小（感觉都不应该称为反演，，实在没啥应用）
但在某些情况下，用欧拉反演推式子确实会简单很多
首先给出 \(\sum\limits_{d\mid n}\varphi(d)=n\) 的证明：
首先有 \(\sum\limits_{d\mid n}\sum\limits_{i=1}^n[\gcd(i,n)=d]=n\)
其中的方括号是艾佛森括号
这个式子其实是将 \(1\sim n\) 的所有整数 \(i\) 按 \(\gcd(i,n)\) 的值分类
每个 \(i\) 都只会在 \(d=\gcd(i,n)\) 处产生恰好一次贡献，故左式的值为 \(n\)
简单地推一推式子：
\(\begin{aligned}
\sum_{d\mid n}\sum_{i=1}^n[\gcd(i,n)=d]=n &\Rightarrow\\
\sum_{d\mid n}\sum_{i=1}^{n/d}[\gcd(i,n/d)=1]=n &\Rightarrow\\
\sum_{d\mid n}\varphi(n/d)=n&\Rightarrow\\
\sum_{d\mid n}\varphi(d)=n&
\end{aligned}\)
结论得证
然后你只要会用这个结论就行了
习题
主要是应用于 \(\gcd\) 求和形式的式子，直接把 \(\gcd\) 换成 \(\sum\limits_{d\mid \gcd}\varphi(d)\) ，然后大力推一波即可
[NOI2010] 能量采集（洛谷P1447）
SP26017 GCDMAT - GCD OF MATRIX
SP26045 GCDMAT2 - GCD OF MATRIX (hard)（毒瘤卡常题）
AT5310 [ABC162E] Sum of gcd of Tuples (Hard)
LibreOJ #6491. 「XXOI 2018」简单的最大公约数 （需用杜教筛）