一、莫比乌斯反演涉及知识 1.莫比乌斯函数 2.莫比乌斯的线性筛法 3.狄利克雷卷积 4.莫比乌斯反演详解 5.整除法分块 6.杜教筛
二、μ 莫比乌斯函数定义
μ ( n ) = { 1 n=1 ( − 1 ) k n= P1*P2*P3*...*Pk(其中P是质数) 0 else其他情况 μ(n)=begin{cases} 1& text{n=1}\ (-1)^k& text{n= P1*P2*P3*...*Pk(其中P是质数)}\ 0& text{else其他情况} end{cases} μ(n)=⎩⎪⎨⎪⎧1(−1)k0n=1n= P1*P2*P3*...*Pk(其中P是质数)else其他情况
也就是说如果n有平方质因子的话就为0。
三、莫比乌斯线性筛
代码语言：javascript复制int prime[MAXN],prime_tot;
bool isprime[MAXN];
int mu[MAXN];
void pre_calc(int limt)
{
mu[1]=1;
for(int i=2;i<=limt;i )
{
if(!isprime[i]){
prime[prime_tot]=i;
mu[i]=-1;
}
for (int j=1;j<prime_tot;j )
{
if(i*prime[j]>lim) break;
isprime[i*prime[j]]= ture;
if(i %prime[j]==0) {
mu[i*prime[j]]=0;
break;
}else{
mu[i*prime[j]]=-mu[i];
}
}
}
}四、狄利克雷卷积 (f*g)(n)= ∑ d ∣ n f ( d ) g ( n d ) sum_{d|n}f(d)g( frac{n}{d}) ∑d∣nf(d)g(dn)
积性函数指对于所有互质的整数a和b有性质f(a*b)=f(a)f(b)的数论函数。 完全积性函数不需要互质既有f(ab)=f(a) * f(b)
欧 拉 函 数 φ ( n ) 莫 比 乌 斯 函 数 ， 关 于 非 平 方 数 的 质 因 子 数 目 μ ( n ) 最 大 公 因 子 ， 当 k 固 定 的 情 况 g c d ( n , k ) 单 位 函 数 I d ( n ) = n 不 变 函 数 1 ( n ) = n 因 子 数 目 d ( n ) d = 1 ∗ 1 因 子 之 和 函 数 σ ( n ) σ = 1 ∗ I d 因 子 函 数 σ k ( n ) 幂 函 数 I d k ( n ) = n k 狄 利 克 雷 卷 积 单 位 元 ε = [ n = = 1 ] 当 n = 1 时 ε = 1 其 他 等 于 0 刘 维 尔 函 数 λ ( n ) 关 于 能 整 除 n 的 质 因 子 的 数 目 欧拉函数 φ(n) \ 莫比乌斯函数，关于非平方数的质因子数目μ(n) \ 最大公因子，当k固定的情况 gcd(n,k) \ 单位函数Id(n)=n\ 不变函数 1(n) =n\ 因子数目 d(n) d=1*1\ 因子之和函数σ(n) σ=1*Id\ 因子函数 σk(n) \ 幂函数Idk(n)=n^k\ 狄利克雷卷积单位元ε=[n==1] 当n=1时ε=1其他等于0 \ 刘维尔函数 λ(n) 关于能整除n的质因子的数目 欧拉函数φ(n)莫比乌斯函数，关于非平方数的质因子数目μ(n)最大公因子，当k固定的情况gcd(n,k)单位函数Id(n)=n不变函数1(n)=n因子数目d(n)d=1∗1因子之和函数σ(n)σ=1∗Id因子函数σk(n)幂函数Idk(n)=nk狄利克雷卷积单位元ε=[n==1] 当n=1时ε=1其他等于0刘维尔函数λ(n)关于能整除n的质因子的数目
定理 μ*1=ε
五、莫比乌斯反演
莫比乌斯反演的公式就在上面，通过好确定的g(n)简化对f(n) 的 求解就是莫比乌斯反演的精髓，而狄利克雷卷积就是到处这个公式（即证明的主要方法）
