今天一共4张图图最多的一集
推歌：勾指起誓/洛天依 by ilem
突然发现自己的闲话风格受了别人很大影响，看了lxyt-415x和jijidawang导致开始写闲话，然后看了crimson和lxyt-415x的闲话导致开始放图，最开始推歌忘了和谁学的然后后来和HS_xh\jijidawang\crimson学的不放歌词了，唯一不变的就是只有我最菜
今天先不学平衡树，直接上莫比乌斯函数
但是很不好，OI-wiki说要先学数论分块和狄利克雷卷积，但是非常恼虽然数论分块有所了解但是狄利克雷卷积是个啥？而且看别人的博客好像也没提狄利克雷卷积那么因为OJ上面把这个放到了AC自动机之前所以肯定得学直接不管三七二十几直接上了
莫比乌斯函数
\(\mu\) 为莫比乌斯函数(\(\mathcal{Möbius}\))
-
定义:
\[\mu(n)= \begin{cases} 1 &n=1\\ 0 &n含有平方因子\\ (-1)^k &k为n的本质不同质因子个数\\ \end{cases} \]感觉定义上类似欧拉函数
看起来这个式子很奇怪，所以用我浅薄的知识储备把它变成文字叙述如果错了请大佬指正
首先当 \(n=1\) 时 \(\mu(n) = 1\)
然后用唯一分解定理可以得到 \(n=\prod_{i=1}^{k}{p_i}^{c_i}\)，如果 \(\exists\ c_i \ne 1(c_i \in \{c_1,c_2,\cdots,c_k \})\) 则\(\mu(n)=0\)
否则 \(\mu(n)=(-1)^k\)
看起来不是很难的样子
-
性质：
-
对于任意正整数 \(n\) ：
\[\sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} \]-
证明(几乎照搬\(\text{OI-wiki}\))
假设
\[\ n=\prod_{i=1}^k{p_i}^{c_i} \]\[n'=\prod_{i=1}^k p_i \]那么
\[\begin{cases} \sum_{d\mid n}\mu(d) =\sum_{i=0}^k \binom{k}{i}\times(-1)^i =(1+(-1))^k \\ \\ \sum_{d\mid n'}\mu(d) =\sum_{i=0}^k \binom{k}{i}\times(-1)^i =(1+(-1))^k \end{cases} \]我们发现其实
\[\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k \binom{k}{i}\times(-1)^i=(1+(-1))^k \]根据二项式定理，易知该式子的值在 \(k=0\) 即 \(n=1\) 时值为 \(1\) 否则为 \(0\) ，
-
-
对于任意正整数 \(n\)
\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} \]
-
-
实现：
众所周知，线性筛可以求好多积性函数
那么求\(\mathcal{Möbius}\)函数的方法就很显然了( \(\mathcal{Möbius}\)函数是积性函数 )
线性筛
class MoBIUS{ public: int mu[MAXM],p[MAXM],tot; bool f[MAXM]; void Mobius(int n){ mu[1]=1; for(int i=2;i<=n;++i){ if(!f[i]) p[++tot]=i, mu[i]=-1; for(int j=1;(j<=tot&&i*p[j]<=n);++j){ f[i*p[j]]=1; if(i%p[j]==0){ mu[i*p[j]]=0; break; } mu[i*p[j]]=-mu[i]; } } } }Mu;
那么有了求\(\mathcal{Möbius}\)函数的方法了，但是还是做不出来题怎么办
所以选择学莫比乌斯反演
