莫比乌斯函数定义

$\mu (n)=\{\begin{array}{ll}1& n=1\\ (-1{)}^k& n=p_1{p}_2{p}_3\dots p_k\\ 0& p^2|n\end{array}$

其中所有的$p$都是关于$n$的质因数

莫比乌斯函数性质

当$\sum _{d|n}\mu (d)=[n=1]$

其中方括号是艾佛森表示法,类似于条件表达式,当表达式成立时表达式的值为$1$,否则表达式的值为$0$

当$n=1$时,可以直接计算得出$\sum _{d|1}\mu (d)=\mu (1)=1$

当$n\ne 1$时,对$n$进行质因数分解可以得到$n=p_1^{a_1}{p}_2^{a_2}{p}_3^{a_3}\cdots p_k^{a_k}$

此时$d$质因数分解后,若有任何的$a$大于$1$的情况,那么此时的$\mu (d)=0$,并不会对结果造成任何的影响

我们设$m=p_1{p}_2{p}_3\cdots p_k$

可得$\sum _{d|m}\mu (d)=\sum _{d|n}\mu (d)$

因为现在的$m$是由不同的质因数乘积而成的

所以$m$的因数$d$由$t(t\le k)$个$m$的不同的质因数乘积而成

那么此时的$\mu (d)$值为$(-1{)}^t$

这样的$t$值有$C_k^t$个

因此$\sum _{d|m}\mu (d)=\sum _{t=1}^k{C}_k^t(-1{)}^t$

可以对增加一项关于$1$的乘积$\sum _{t=1}^k{C}_k^t(-1{)}^t=\sum _{t=1}^k{C}_k^t(-1{)}^t{1}^{k-t}$

根据二项式定理$(x+y{)}^k=\sum _{i=1}^k\left(\begin{array}{c}k\\ i\end{array}\right)x^i{y}^{k-i}=(x+y{)}^k=\sum _{i=1}^k{C}_k^i{x}^i{y}^{k-i}$

式子即为$\sum _{t=1}^k{C}_k^t(-1{)}^t{1}^{k-t}=((-1)+1{)}^k=0^k=0$

$\sum _{d|n}\mu (d)=\sum _{d|m}\mu (d)=\sum _{t=1}^k{C}_k^t(-1{)}^t=\sum _{t=1}^k{C}_k^t(-1{)}^t{1}^{k-t}=((-1)+1{)}^k=0^k=0$

莫比乌斯函数公式

公式一

若有$F(n)=\sum _{d|n}f(d)$,表示为$F$函数是$f$函数的约数和

那么$f(n)=\sum _{d|n}\mu (d)F(\frac{n}{d})$

将$F(n)=\sum _{d|n}f(d)$代入到$f(n)=\sum _{d|n}\mu (d)F(\frac{n}{d})$

$f(n)=\sum _{d|n}\mu (d)\sum _{p|(n/d)}f(p)$

改变式子的枚举顺序,那么$\sum _{d|n}\mu (d)\sum _{p|(n/d)}f(p)=\sum _{p|n}f(p)\sum _{d|(n/p)}\mu (d)$

根据莫比乌斯函数的性质,当$n/p=1$时$\sum _{d|(n/p)}\mu (d)$为$1$,其余情况为$0$

此时的$p$为$n$,$f(n)\ast 1=f(n)$

所以$\sum _{p|n}f(p)\sum _{d|(n/p)}\mu (d)=f(n)$

$f(n)=\sum _{d|n}\mu (d)F(\frac{n}{d})=\sum _{d|n}\mu (d)\sum _{p|(n/d)}f(p)=\sum _{p|n}f(p)\sum _{d|(n/p)}\mu (d)=f(n)$

公式二

若有$F(n)=\sum _{n|d}f(d)$,表示为$F$函数是$f$函数的倍数和

那么$f(n)=\sum _{n|d}\mu (d)F(\frac{d}{n})=\sum _{n|d}\mu (\frac{d}{n})F(d)$

将$F(n)=\sum _{n|d}f(d)$代入到$f(n)=\sum _{n|d}\mu (\frac{d}{n})F(d)$

$f(n)=\sum _{n|d}\mu (\frac{d}{n})\sum _{d|p}f(p)$

改变式子的枚举顺序,那么$\sum _{n|d}\mu (\frac{d}{n})\sum _{d|p}f(p)=\sum _{n|p}f(p)\sum _{d|(p/n)}\mu (d)$

根据莫比乌斯函数的性质,当$p/n=1$时$\sum _{d|(p/n)}\mu (d)$为$1$,其余情况为$0$

所以$\sum _{n|p}f(p)\sum _{d|(p/n)}\mu (d)=f(n)$

$f(n)=\sum _{n|d}\mu (d)F(\frac{d}{n})=\sum _{n|d}\mu (\frac{d}{n})F(d)=\sum _{n|d}\mu (\frac{d}{n})\sum _{d|p}f(p)=\sum _{n|p}f(p)\sum _{d|(p/n)}\mu (d)=f(n)$

莫比乌斯函数求法

埃氏筛

埃氏筛的时间复杂度$O(nlogn)$,$1e7$以内的数据可以解决

以下是求$1$到$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];

欧拉筛

因为莫比乌斯函数是一个积性函数,所以可以通过欧拉筛来求

欧拉筛的时间复杂度比较优秀,$1e7$以内的数据可以快速解决

以下是求$1$到$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));}
}