\(前置技能\)
- 学会莫比乌斯函数必须要先知道狄利克雷函数
以及什么是逆元（一本正经胡说八道）
\(狄利克雷卷积\)
两个函数 \(f,g\)\(\begin{aligned}f*g(n)=\sum_{d|n}^nf(d)g(\frac{n}{d})\end{aligned}\)性质
交换律\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f*g=g*f\)结合律\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f*g*h=f*(g*h)\)加法分配率\(\ \ \ \ \ \ \ \ \ \ f*(g+h)=f*g+f*h\)\(几个定理\)
- ① 定义单位函数\(I(n)=[n=1]\)，即只有当ｎ等于１时，\(I(1)=1\)，其余情况都为０
- ② \(I * f=f\)
- ③ 已知函数\(f\)，定义函数\(f\)的逆\(f^{-1}\)，满足\(f * f^{-1}=I\)，且积性函数的逆也是积性函数
- ④ 由③可得\(f^{-1}(1)=\frac{1}{f(1)}\)
⑤ 令\(\xi(n)=1\)
\(莫比乌斯函数\)
- 莫比乌斯函数 \(\mu=\xi^{-1}\)\(\mu(n)=\xi^{-1}(n)= \left\{\begin{matrix}1 &n=1 \\(-1)^k &a1=a2=\cdots =ak=1&\\ 0&otherwise \end{matrix}\right.\)
\(如何推导\)
\(如何求逆\)
③等价于
\(\begin{aligned}\forall n: \sum_{d|n} f(d)·f^{-1}(\frac nd)=[n=1]\end{aligned}\)\(\begin{aligned}\sum_{d|n}f(d)·f^{-1}(\frac nd)=I(n) (n=\not 1)=0\end{aligned}\)\(f^{-1}(n)·f(1)=-\sum_{d|n,d=\not1}f(d)·f^{-1}(\frac nd)\)\(\begin{aligned}f^{-1}(n)=\frac{-\sum_{d|n,d=\not1}f(d)·f^{-1}(\frac nd)}{f(1)}\end{aligned}\)\(莫比乌斯函数\)
令 \(f=\xi\),\(p\)为质数
\(f^{-1}(1)=1\)\(f^{-1}(p)=\frac{-f(p)·f^{-1}(1)}{f(1)}=-1\)\(f^{-1}(p^2)=-(f(p^2)·f^{-1}(1)+f(p)·f^{-1}(p))=0\)\(f^{-1}(p^3)=-(f(p^3)·f^{-1}(1)+f(p^2)·f^{-1}(p)+f(p)·f^{-1}(p^2))=0\)\(\begin{aligned}f^{-1}(p^k)=-\sum_{i=1}^k f(p^i)·f^{-1}(p^{k-i})\end{aligned}\) 其中只有 \(f(p^k)·f^{-1}(1)=1,f(p^{k-1})·f^{-1}(p)=-1\)，其余项都是0\(f^{-1}(p^k)=\left\{\begin{matrix}-1 & k=1\\0 & k>1 \end{matrix}\right.\)\(n=p_1^{a_1}·p_2^{a_2}·\cdots p_k^{a_k}\) 所以莫比乌斯函数可以推出来了\(\mu(n)=f^{-1}(n)= \left\{\begin{matrix}1 &n=1 \\(-1)^k &a1=a2=\cdots =ak=1&\Leftarrow 积性函数推出 \\ 0&otherwise \end{matrix}\right.\)
\(莫比乌斯函数的性质\)
- \(\mu*\xi=I\) 因为\(\mu=\xi^{-1}\) 所以有\(\begin{aligned}\sum_{d|n}^n\mu(d)=\sum_{d|n}^n\mu·1=\mu*\xi(n)=I(n)=[n=1]\end{aligned}\) 记住这句，下面的证明要用到
- \(I*f=f\)
- \(f*\mu*\xi=f\)
- \(f*\xi=g \Rightarrow f=g*\mu\)
\(线性筛\)
利用积性函数的性质以及\(\mu\)的表达式
int cnt;int prime[maxn],mu[maxn];bool vis[maxn];void mu_sieve (int n){ mu[1]=1; for (int i=2;i<=n;++i){ if (!vis[i]){ prime[++cnt]=i,mu[i]=-1;} for (int j=1;j<=cnt&&i*prime[j]<=n;++j){ vis[i*prime[j]]=true; if (i%prime[j]==0){ mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } }} \(莫比乌斯反演\)
- 若有 \(\begin{aligned}g(n)=\sum_{d|n}f(d)\end{aligned}\) 则有 \(\begin{aligned}f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})g(d)\end{aligned}\)
\(证明\)
法一 \(\begin{aligned} \sum_{d|n}{\mu(d)g(\frac{n}{d})}=\sum_{d|n}{\mu(d)\sum_{x|\frac{n}{d}}{f(x)}}=\sum_{x|n}{f(x)}\sum_{d|\frac{n}{x}}{\mu(d)}=\sum_{x|n}{f(x)[\frac{n}{x}=1]}=f(n) \end{aligned}\) 法二 \(g=f*\xi,f=g*\mu\)
- 若有\(\begin{aligned}g(n)=\sum_{n|d}f(d)\end{aligned}\) 则有\(\begin{aligned}f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)\end{aligned}\)
\(证明\)
\(\begin{aligned}\sum_{n|d}\mu(\frac{d}{n})g(d)=\sum_{k=1}^{+\infty}\mu(k)g(kn)=\sum_{k=1}^{+\infty}\mu(k)\sum_{kn|d}f(d)=\sum_{n|d}f(d)\sum_{k|\frac{d}{n}}\mu(k)=\sum_{n|d}f(d)[\frac{d}{n}=1]=f(n) \end{aligned}\)
\(莫比乌斯反演的应用\)
莫比乌斯函数一般用于\(gcd\)中
\(\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)&=\sum_d^{min(n,m)} d\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d] \\ &=\sum_{d}^{min(n,m)}d\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}[gcd(i,j)=1] \\ &=\sum_{d}^{min(n,m)}d\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}\sum_{k\mid gcd(i,j)}\mu(k) \\ &=\sum_d^{min(n,m)} d\sum_k^{min(\frac{n}{d},\frac{m}{d})}\mu(k)\sum_{k\mid i}^{\frac nd}\sum_{k\mid j}^{\frac md} \\ &=\sum_{d}^{min(n,m)}d\sum_k^{min(\frac{n}{d},\frac{m}{d})}\mu(k)\lfloor \frac n{kd}\rfloor \lfloor\frac m{kd}\rfloor \end{aligned}\) 令\(T=kd\)\(\begin{aligned} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{T}^{min(n,m)}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\sum_{k\mid T}\frac Tk\mu(k)\end{aligned}\) 以上是莫比乌斯反演推出来的式子\(\begin{aligned}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{T}^{min(n,m)}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\varphi(T)\end{aligned}\)
这一步是欧拉反演，证明请移步 当然，这里这个例子不如直接用欧拉反演\(\begin{aligned}\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\varphi(d)\end{aligned}\)如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧