2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion [2020/05/25 01:20] potassium [莫比乌斯函数] add link |
2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion [2020/05/26 10:20] (当前版本) nikkukun add some links |
||
|---|---|---|---|
| 行 257: | 行 257: | ||
| 以下给出一个简单的证明： | 以下给出一个简单的证明： | ||
| - | 上式显然先决定 $x$ 的取值，再决定 $y$ 的取值。对于一个因子 $p$，若 $p^a \mid i,\ p^b \mid j$，且 $p^{a+b} \mid ij$，则 | + | 上式显然先决定 $x$ 的取值，再决定 $y$ 的取值。对于一个质因子 $p$，若 $p^a \mid i,\ p^b \mid j$，且 $p^{a+b} \mid ij$，则由于 $(x, y) = 1$，一定有 $\min(a, b) = 0$，故 |
| - | * $p^0 \mid x$，则表示 $y$ 可以任意选 $p^1, \ldots, p^b$ 等因子，分别映射到因数 $d \mid p^{a+1}, d \mid p^{a+2}, \ldots, d \mid p^{a+b}$； | + | * $p^0 \mid x$，则表示 $y$ 可以任意选 $p^1, \ldots, p^b$ 等因子，分别映射到因数 $p^{a+1}, p^{a+2}, \ldots, p^{a+b}$； |
| - | * $p^1 \mid x, p^2 \mid x, \ldots, p^a \mid x$，则表示 $x$ 可以任意选 $p^1, \ldots, p^a$ 等因子，分别映射到因数 $d \mid p^{1}, d \mid p^{2}, \ldots, d \mid p^{a}$； | + | * $p^1 \mid x, p^2 \mid x, \ldots, p^a \mid x$，则表示 $x$ 可以任意选 $p^1, \ldots, p^a$ 等因子，分别映射到因数 $p^{1}, p^{2}, \ldots, p^{a}$； |
| - | * $p^0 \mid x$ 且 $q^0 \mid y$ 等因子，映射到因数 $d \mid p^0$； | + | * $p^0 \mid x$ 且 $q^0 \mid y$ 等因子，映射到因数 $p^0$； |
| + | |||
| + | 综上，因子 $p^0, p^1, \ldots, p^{a+b}$ 都能被唯一地表示出来且一一对应（双射），因此等式成立。[[..:potassium:sieve | ||
| + | #约数之和|这里]] 提供了另一种关于约数个数和的类似形式证明，但是使用了更合理的映射使得式子易于证明。 | ||
| - | 综上，因子 $p^0, p^1, \ldots, p^{a+b}$ 都能被唯一地表示出来且一一对应（双射），因此等式成立。 | ||
| ===== 练习 ===== | ===== 练习 ===== | ||
2020-2021/teams/i_dont_know_png/nikkukun/mobius_inversion.1590340821.txt.gz · 最后更改: 2020/05/25 01:20 由 potassium
