证:$\displaystyle \sum_{i=1}^n \mu (i)^2 = \sum_{i=1}^{\left \lfloor \sqrt n \right \rfloor}\mu (i)\left \lfloor \frac{n}{i^2} \right \rfloor$, 其中 $\mu (x)$ 为莫比乌斯函数.
分析:
在等式的推到中, 最重要的是理解一个等式的含义.
上式左边其实是求 $1 \sim n$ 中无平方因子数的个数, 右边相当于枚举 $n$ 的平方因子, 再乘以容斥系数.
因此, 也找到了严格证明的方法了.
证:
设 $f(x)$ 为 $x$ 的最大的平方因子.
于是 $\displaystyle \sum_{i=1}^n \mu (i)^2 = \sum_{i=1}^n[f(i)==1]$(最大平方因子为 1).
使用经典套路:
- $$
- \begin{
- aligned
- }
- \sum_{
- i=1
- }^n \mu (i)^2 & = \sum_{
- i=1
- }^n[f(i)==1]\\
- &= \sum_{
- i=1
- }^n\varepsilon(f(i))\\
- &= \sum_{
- i=1
- }^n\sum_{
- d|f(i)
- }\mu (d)
- \end{
- aligned
- }$$
改变枚举顺序:
- $$
- \begin{
- aligned
- }
- \sum_{
- i=1
- }^n\sum_{
- d|f(i)
- }\mu(d) & = \sum_{
- d=1
- }^n \mu (d)\sum_{
- i=1
- }^n d^2 | i\\
- &= \sum_{
- d=1
- }^n \mu (d)\left \lfloor \frac{
- n
- }{
- d^2
- } \right \rfloor \\
- &= \sum_{
- d=1
- }^{
- \sqrt n
- } \mu (d)\left \lfloor \frac{
- n
- }{
- d^2
- } \right \rfloor
- \end{
- aligned
- }$$
证毕
参考链接: https://zhuanlan.zhihu.com/p/36745053
来源: http://www.bubuko.com/infodetail-3162494.html