数论函数玄学操作

数论函数推式子是真的玄学， 乱七八糟的一脸懵逼， 好不容易看懂了转身又 tm 忘了， 这里列出一些我见过的。

持续更新。

update: 证明都删掉了，这是篇整理，目的是让结论更一目了然。需要证明联系我我免费讲解

常见数论函数卷积

\[ \mu \cdot I = \epsilon \]

\[ \phi \cdot I = id \]

\[ \mu \cdot id = \phi \]

\[ id \cdot I = \sigma \]

常见数论函数 f(ij) 化简

\[ d(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] \]

\[ \sum_{d|ij} f(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] f(\frac{iy}{x}) \]

\[ \phi(i \cdot j) = \phi(i) \phi(j) \frac{gcd(i, j)}{\phi(gcd(i, j))} \]

常见数论函数求和

\[ \sum_{i=1}^n d(i) = \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \]

互质条件转换

\[ [gcd(i, j) = 1] = \sum_{d|i,d|j} \mu(d) \]

\[ \sum_{i=1}^n \sum_{j=1}^m f(i, j) [gcd(i, j) = 1] = \sum_{d=1}^{min(n, m)} \mu(d) \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} f(id, jd) \]