![[莫比乌斯反演]莫比乌斯函数](https://1000zi.500zi.com/uploadfile/img/15/13/fc5345097b3032d52c770d55381f4188.jpg)
莫比乌斯函数定义
μ ( n ) = { 1 n = 1 ( − 1 ) k n = p 1 p 2 p 3 … p k 0 p 2 ∣ n \mu(n)=\begin{cases}1&n=1\\(-1)^k&n=p_1p_2p_3…p_k\\0&p^2|n\end{cases} μ(n)=⎩ ⎨ ⎧1(−1)k0n=1n=p1p2p3…pkp2∣n
其中所有的 p p p都是关于 n n n的质因数
莫比乌斯函数性质
当 ∑ d ∣ n μ ( d ) = [ n = 1 ] \sum\limits_{d|n}\mu(d)=[n=1] d∣n∑μ(d)=[n=1]
其中方括号是艾佛森表示法,类似于条件表达式,当表达式成立时表达式的值为 1 1 1,否则表达式的值为 0 0 0
当 n = 1 n=1 n=1时,可以直接计算得出 ∑ d ∣ 1 μ ( d ) = μ ( 1 ) = 1 \sum\limits_{d|1}\mu(d)=\mu(1)=1 d∣1∑μ(d)=μ(1)=1
当 n ≠ 1 n\neq 1 n=1时,对 n n n进行质因数分解可以得到 n = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p k a k n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k} n=p1a1p2a2p3a3⋯pkak
此时 d d d质因数分解后,若有任何的 a a a大于 1 1 1的情况,那么此时的 μ ( d ) = 0 \mu(d)=0 μ(d)=0,并不会对结果造成任何的影响
我们设 m = p 1 p 2 p 3 ⋯ p k m=p_1p_2p_3\cdots p_k m=p1p2p3⋯pk
可得 ∑ d ∣ m μ ( d ) = ∑ d ∣ n μ ( d ) \sum\limits_{d|m}\mu(d)=\sum\limits_{d|n}\mu(d) d∣m∑μ(d)=d∣n∑μ(d)
因为现在的 m m m是由不同的质因数乘积而成的
所以 m m m的因数 d d d由 t ( t ≤ k ) t(t\leq k) t(t≤k)个 m m m的不同的质因数乘积而成
那么此时的 μ ( d ) \mu(d) μ(d)值为 ( − 1 ) t (-1)^t (−1)t
这样的 t t t值有 C k t C_k^t Ckt个
因此 ∑ d ∣ m μ ( d ) = ∑ t = 1 k C k t ( − 1 ) t \sum\limits_{d|m}\mu(d)=\sum\limits_{t=1}^{k}C_k^t(-1)^t d∣m∑μ(d)=t=1∑kCkt(−1)t
可以对增加一项关于 1 1 1的乘积 ∑ t = 1 k C k t ( − 1 ) t = ∑ t = 1 k C k t ( − 1 ) t 1 k − t \sum\limits_{t=1}^{k}C_k^t(-1)^t=\sum\limits_{t=1}^{k}C_k^t(-1)^t 1^{k-t} t=1∑kCkt(−1)t=t=1∑kCkt(−1)t1k−t
根据二项式定理 ( x + y ) k = ∑ i = 1 k ( k i ) x i y k − i = ( x + y ) k = ∑ i = 1 k C k i x i y k − i (x+y)^k=\sum\limits_{i=1}^{k}\begin{pmatrix}k\\i\end{pmatrix}x^iy^{k-i}=(x+y)^k=\sum\limits_{i=1}^{k}C_k^ix^iy^{k-i} (x+y)k=i=1∑k(ki)xiyk−i=(x+y)k=i=1∑kCkixiyk−i
式子即为 ∑ t = 1 k C k t ( − 1 ) t 1 k − t = ( ( − 1 ) + 1 ) k = 0 k = 0 \sum\limits_{t=1}^{k}C_k^t(-1)^t 1^{k-t}=((-1)+1)^k=0^k=0 t=1∑kCkt(−1)t1k−t=((−1)+1)k=0k=0
∑ d ∣ n μ ( d ) = ∑ d ∣ m μ ( d ) = ∑ t = 1 k C k t ( − 1 ) t = ∑ t = 1 k C k t ( − 1 ) t 1 k − t = ( ( − 1 ) + 1 ) k = 0 k = 0 \sum\limits_{d|n}\mu(d)=\sum\limits_{d|m}\mu(d)=\sum\limits_{t=1}^{k}C_k^t(-1)^t=\sum\limits_{t=1}^{k}C_k^t(-1)^t 1^{k-t}=((-1)+1)^k=0^k=0 d∣n∑μ(d)=d∣m∑μ(d)=t=1∑kCkt(−1)t=t=1∑kCkt(−1)t1k−t=((−1)+1)k=0k=0
莫比乌斯函数公式
公式一
若有 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum\limits_{d|n}f(d) F(n)=d∣n∑f(d),表示为 F F F函数是 f f f函数的约数和
那么 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum\limits_{d|n}\mu(d)F(\frac{n}{d}) f(n)=d∣n∑μ(d)F(dn)
将 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum\limits_{d|n}f(d) F(n)=d∣n∑f(d)代入到 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum\limits_{d|n}\mu(d)F(\frac{n}{d}) f(n)=d∣n∑μ(d)F(dn)
f ( n ) = ∑ d ∣ n μ ( d ) ∑ p ∣ ( n / d ) f ( p ) f(n)=\sum\limits_{d|n}\mu(d)\sum\limits_{p|(n/d)}f(p) f(n)=d∣n∑μ(d)p∣(n/d)∑f(p)
改变式子的枚举顺序,那么 ∑ d ∣ n μ ( d ) ∑ p ∣ ( n / d ) f ( p ) = ∑ p ∣ n f ( p ) ∑ d ∣ ( n / p ) μ ( d ) \sum\limits_{d|n}\mu(d)\sum\limits_{p|(n/d)}f(p)=\sum\limits_{p|n}f(p)\sum\limits_{d|(n/p)}\mu(d) d∣n∑μ(d)p∣(n/d)∑f(p)=p∣n∑f(p)d∣(n/p)∑μ(d)
根据莫比乌斯函数的性质,当 n / p = 1 n/p=1 n/p=1时 ∑ d ∣ ( n / p ) μ ( d ) \sum\limits_{d|(n/p)}\mu(d) d∣(n/p)∑μ(d)为 1 1 1,其余情况为 0 0 0
此时的 p p p为 n n n, f ( n ) ∗ 1 = f ( n ) f(n)*1=f(n) f(n)∗1=f(n)
所以 ∑ p ∣ n f ( p ) ∑ d ∣ ( n / p ) μ ( d ) = f ( n ) \sum\limits_{p|n}f(p)\sum\limits_{d|(n/p)}\mu(d)=f(n) p∣n∑f(p)d∣(n/p)∑μ(d)=f(n)
f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) = ∑ d ∣ n μ ( d ) ∑ p ∣ ( n / d ) f ( p ) = ∑ p ∣ n f ( p ) ∑ d ∣ ( n / p ) μ ( d ) = f ( n ) f(n)=\sum\limits_{d|n}\mu(d)F(\frac{n}{d})=\sum\limits_{d|n}\mu(d)\sum\limits_{p|(n/d)}f(p)=\sum\limits_{p|n}f(p)\sum\limits_{d|(n/p)}\mu(d)=f(n) f(n)=d∣n∑μ(d)F(dn)=d∣n∑μ(d)p∣(n/d)∑f(p)=p∣n∑f(p)d∣(n/p)∑μ(d)=f(n)
公式二
若有 F ( n ) = ∑ n ∣ d f ( d ) F(n)=\sum\limits_{n|d}f(d) F(n)=n∣d∑f(d),表示为 F F F函数是 f f f函数的倍数和
那么 f ( n ) = ∑ n ∣ d μ ( d ) F ( d n ) = ∑ n ∣ d μ ( d n ) F ( d ) f(n)=\sum\limits_{n|d}\mu(d)F(\frac{d}{n})=\sum\limits_{n|d}\mu(\frac{d}{n})F(d) f(n)=n∣d∑μ(d)F(nd)=n∣d∑μ(nd)F(d)
将 F ( n ) = ∑ n ∣ d f ( d ) F(n)=\sum\limits_{n|d}f(d) F(n)=n∣d∑f(d)代入到 f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})F(d) f(n)=n∣d∑μ(nd)F(d)
f ( n ) = ∑ n ∣ d μ ( d n ) ∑ d ∣ p f ( p ) f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})\sum\limits_{d|p}f(p) f(n)=n∣d∑μ(nd)d∣p∑f(p)
改变式子的枚举顺序,那么 ∑ n ∣ d μ ( d n ) ∑ d ∣ p f ( p ) = ∑ n ∣ p f ( p ) ∑ d ∣ ( p / n ) μ ( d ) \sum\limits_{n|d}\mu(\frac{d}{n})\sum\limits_{d|p}f(p)=\sum\limits_{n|p}f(p)\sum\limits_{d|(p/n)}\mu(d) n∣d∑μ(nd)d∣p∑f(p)=n∣p∑f(p)d∣(p/n)∑μ(d)
根据莫比乌斯函数的性质,当 p / n = 1 p/n=1 p/n=1时 ∑ d ∣ ( p / n ) μ ( d ) \sum\limits_{d|(p/n)}\mu(d) d∣(p/n)∑μ(d)为 1 1 1,其余情况为 0 0 0
所以 ∑ n ∣ p f ( p ) ∑ d ∣ ( p / n ) μ ( d ) = f ( n ) \sum\limits_{n|p}f(p)\sum\limits_{d|(p/n)}\mu(d)=f(n) n∣p∑f(p)d∣(p/n)∑μ(d)=f(n)
f ( n ) = ∑ n ∣ d μ ( d ) F ( d n ) = ∑ n ∣ d μ ( d n ) F ( d ) = ∑ n ∣ d μ ( d n ) ∑ d ∣ p f ( p ) = ∑ n ∣ p f ( p ) ∑ d ∣ ( p / n ) μ ( d ) = f ( n ) f(n)=\sum\limits_{n|d}\mu(d)F(\frac{d}{n})=\sum\limits_{n|d}\mu(\frac{d}{n})F(d)=\sum\limits_{n|d}\mu(\frac{d}{n})\sum\limits_{d|p}f(p)=\sum\limits_{n|p}f(p)\sum\limits_{d|(p/n)}\mu(d)=f(n) f(n)=n∣d∑μ(d)F(nd)=n∣d∑μ(nd)F(d)=n∣d∑μ(nd)d∣p∑f(p)=n∣p∑f(p)d∣(p/n)∑μ(d)=f(n)
莫比乌斯函数求法
埃氏筛
埃氏筛的时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn), 1 e 7 1e7 1e7以内的数据可以解决
以下是求 1 1 1到 n n n的莫比乌斯函数和莫比乌斯函数前缀和的埃氏筛的写法
Pr[1]=1;for(int i=1;i<=t;i++)Mu[i]=1;for(int i=2;i<=t;i++){if(Prz[i]==0){P++;Pr[P]=i;for(int j=i;j<=t;j+=i){Prz[j]=1;if(j%(i*i)==0){Mu[j]=0;}Mu[j]=-Mu[j];}}}PreMu[0]=0;for(int i=1;i<=t;i++)PreMu[i]=PreMu[i-1]+Mu[i];
欧拉筛
因为莫比乌斯函数是一个积性函数,所以可以通过欧拉筛来求
欧拉筛的时间复杂度比较优秀, 1 e 7 1e7 1e7以内的数据可以快速解决
以下是求 1 1 1到 n n n的莫比乌斯函数和莫比乌斯函数前缀和的欧拉筛的写法
Prz[1]=1;Mu[1]=1;for(int i=2;i<=t;i++){if(Prz[i]==0){P++;Pr[P]=i;Mu[i]=-1;}for(int j=1,k;i*Pr[j]<=t&&j<=P;j++){k=i*Pr[j];Prz[k]=1;if(i%Pr[j]==0){Mu[k]=0;break;}Mu[k]=Mu[i]*Mu[Pr[j]];}}PreMu[0]=0;for(int i=1;i<=t;i++)PreMu[i]=PreMu[i-1]+Mu[i];
杜教筛
利用杜教筛可以处理较大的积性函数前缀和的值
例如莫比乌斯函数和欧拉函数
#include<bits/stdc++.h>using namespace std;long long T,n,N,M=8000000,Fz[8000005],Mz[8000005];map<long long,long long>Fd,Md;int P=0,Fk[8000005],Mk[8000005],Pr[8000005],Pv[8000005];void YCL(){Fk[1]=1;Mk[1]=1;for(int i=2;i<=M;i++){if(Pv[i]==0){P++;Pr[P]=i;Fk[i]=i-1;Mk[i]=-1;}for(int j=1,k;j<=P&&i*Pr[j]<=M;j++){k=i*Pr[j];Pv[k]=1;if(i%Pr[j]==0){Fk[k]=Fk[i]*Pr[j];Mk[k]=0;break;}Fk[k]=Fk[i]*Fk[Pr[j]];Mk[k]=Mk[i]*Mk[Pr[j]];}}for(int i=1;i<=M;i++)Fz[i]=Fz[i-1]+Fk[i],Mz[i]=Mz[i-1]+Mk[i];return;}long long DjsF(long long t){if(t<=M)return Fz[t];else if(Fd.count(t))return Fd[t];else{long long s=0;for(long long i,j=2;j<=t;j=i+1){i=t/(t/j);s+=DjsF(t/i)*(i-j+1);}return Fd[t]=t*(t+1)/2-s;}return 0;}long long DjsM(long long t){if(t<=M)return Mz[t];else if(Md.count(t))return Md[t];else{long long s=0;for(long long i,j=2;j<=t;j=i+1){i=t/(t/j);s+=DjsM(t/i)*(i-j+1);}return Md[t]=1-s;}return 0;}int main(){YCL();scanf("%lld",&T);while(T--){scanf("%lld",&n);printf("%lld %lld\n",DjsF(n),DjsM(n));}}
