莫比乌斯函数的证明
资料来源:https://blog.****.net/Danliwoo/article/details/51866867
遗忘是可怕的东西……好记性不如烂笔头讲真……
命题
现在假设我不知道什么是莫比乌斯函数,只知道
若已知F(x)F(x),求f(x)f(x)的表达式。
性质
从已知的关系,可以得到性质:
1. 若y|x(y<x)y|x(y<x),则F(y)F(y)包含的所有f(d)f(d)都被F(x)F(x)包含了,F(y)F(y)不能包含f(x)f(x)
2. 包含f(x)f(x)的最小项是F(x)F(x)
构造
yiyi | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 12 | 15 | 18 | 20 | 30 | 36 | 45 | 60 | 90 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a17a17 | -1 | -1 | -1 | 0 | -1 | -1 | -1 | -1 | 0 | -1 | -1 | 0 | -1 | 0 | -1 | 0 | -1 |
a16a16 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | -1 | -1 | -1 | 0 | -1 | -1 | 0 | 0 | -1 | 0 |
a15a15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a14a14 | -1 | -1 | -1 | -1 | 0 | -1 | -1 | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 |
a13a13 | +1 | +1 | +1 | 0 | +1 | +1 | 0 | +1 | 0 | +1 | 0 | 0 | +1 | 0 | 0 | 0 | 0 |
a12a12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a11a11 | +1 | +1 | +1 | 0 | 0 | +1 | +1 | 0 | 0 | 0 | +1 | 0 | 0 | 0 | 0 | 0 | 0 |
a10a10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a9a9 | +1 | +1 | +1 | +1 | 0 | +1 | 0 | 0 | +1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a8a8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a7a7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a6a6 | -1 | -1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a5a5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a4a4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a3a3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a2a2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
a1a1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
朴素证明