数论函数玄学操作

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

莫比乌斯函数与恒等函数卷积

$$ \mu * I = \epsilon $$

证明

莫比乌斯函数的构造意义。

欧拉函数与恒等函数卷积

$$ \phi * I = id $$

单位函数恒等函数卷积

$$ id * I = \sigma $$

互质条件转换为莫比乌斯函数求和

$$ [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) $$

证明 1

$$ \because [gcd(i, j) == 1] = \epsilon(gcd(i, j)) $$
$$ \because \epsilon = \mu * I $$
$$ \therefore [gcd(i, j) == 1] = \sum_{d|gcd(i, j)} \mu(d) $$
$$ \therefore [gcd(i, j) == 1] = \sum_{d|i,d|j} \mu(d) $$

证明 2

通过容斥原理和莫比乌斯函数的定义可以得出。

约数个数函数转换为互质数对求和

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

整除

$$ \lfloor \frac{a}{\lfloor \frac{b}{c} \rfloor} \rfloor = \lfloor \frac{a}{bc} \rfloor $$


发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: