莫比乌斯反演总结
Alioth_
2019-02-16 15:28:32
## 莫比乌斯反演
其实就是
## $g(x)=f(x)\times1$
## $f(x)=g(x)/1$
只不过乘是狄利克雷卷积 除是乘以1的逆即$μ$
## 几个常用的函数:
1.$\phi(n)$ 欧拉函数
2.$id(n)=n$
3.$\mu$莫比乌斯函数 (1的逆)
4.$\epsilon(n)=[n=1]$
5.$\sigma(n)\ n$的约数个数
已知：$\epsilon=\mu\times 1$ $\ \ \ \ \ $ $id=\phi\times 1$ $\ \ \ \ \ id^k$的逆是$\mu(n)n^k$
## 两种写法
### **形式$A$：**
## $g(x)=\sum\limits_{d|x}{f(d)}$
## $f(x)=\sum\limits_{d|x}{μ(\frac{x}{d})*g(d)}$
### 形式$B$：
## $g(x)=\sum\limits_{x|d}^{n}{f(d)}$
## $f(x)=\sum\limits_{x|d}^{n}{μ(\frac{d}{x})*g(d)}$
## 应用
对于一般的题 比如让化简一个式子等 我们也有两种处理方式
### 1.直接化简
我们直接提$gcd$ 反演如$[gcd(i,j)=1]$这个式子 然后把用$μ$表示出的新式子直接带入化简
注意化简$\sum$时**核心是考虑贡献** 若内层与外层无关 则可以直接提出来 若有关 则需要计算贡献后提出来即再套上个中括号判断成立条件后提出来 有个技巧就是可以改变枚举对象 如枚举因数 枚举$gcd$ 用换元法替代枚举等
**这种情况一般用形式$A$**
### 2.反演整个式子
这种方法比较巧妙和简单 运算量也不高 但比较难想
首先令$f(x)$表示要求的整个式子 然后令$g(x)$等于$f(x)*1$ 对$g(x)$进行化简 然后再用$g(x)$反演回$f(x)$
或者 有些题不好求出$f(x)$ 但我们可以轻易求出$g(x)=\sum\limits_{x|d}^{n}{f(d)}$的答案 这时候我们再反演回去 也可以得到$f(x)$的值
如$P3172$选数
**题意**：求从区间$[L,H]$（$L$和$H$为整数）中选取$N$个整数，使它们的$gcd$为$K$的方案总数模$1000000007$的值。
这里 我们先把$L$ $H$都除以$K$ 问题就转化为选出几个数使$gcd$为$1$ 当然 可以直接化简 但这里可以这样做
令$F(i)$为选数的$gcd$为$i$的倍数的方案总数，则显然 $F(i)=(\lfloor\frac{r}{i}\rfloor-\lfloor\frac{l}{i}\rfloor)^N$
令$f(i)$为选数的$gcd$为$i$的方案总数，则显然$F(i)=\sum\limits_{i|d}f(d)$
这里就很巧妙了 让形式$B$的莫比乌斯反演转化到了实际问题上！我们只需反演出$f$函数即可
两种形式需要看情况选用
## 几个工具
### 1.线性筛 可以筛积性函数
```cpp
void pre()//线性筛预处理n^2/3项的前缀和
{
zs[1]=true;//合数
mu[1]=phi[1]=1;
for(int i=2;i<=MAX;++i)
{
if(!zs[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=tot&&i*pri[j]<=MAX;++j)
{
zs[i*pri[j]]=true;
//这两句判断pri[j]的次数
if(i%pri[j])mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];//pri[j]比i中的任何质因子都小 所以pri[j]是i*pri[j]中的最小质因数
else{mu[i*pri[j]]=0;phi[i*pri[j]]=phi[i]*pri[j];break;}//找到i的最小质因子pri[j] 如果再往后筛 pri[j]就不是i*pri[j]的最小质因子 有可能在i里
}
}
for(int i=1;i<=MAX;++i)phi[i]+=phi[i-1];
for(int i=1;i<=MAX;++i)mu[i]+=mu[i-1];
}
```
### 2.杜教筛 可以更快速求积性函数前缀和
```cpp
void pre()//线性筛预处理n^2/3项的前缀和
{
zs[1]=true;//合数
mu[1]=phi[1]=1;
for(int i=2;i<=MAX;++i)
{
if(!zs[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=tot&&i*pri[j]<=MAX;++j)
{
zs[i*pri[j]]=true;
//这两句判断pri[j]的次数
if(i%pri[j])mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];//pri[j]比i中的任何质因子都小 所以pri[j]是i*pri[j]中的最小质因数
else{mu[i*pri[j]]=0;phi[i*pri[j]]=phi[i]*pri[j];break;}//找到i的最小质因子pri[j] 如果再往后筛 pri[j]就不是i*pri[j]的最小质因子 有可能在i里
}
}
for(int i=1;i<=MAX;++i)phi[i]+=phi[i-1];
for(int i=1;i<=MAX;++i)mu[i]+=mu[i-1];
}
ll Mu(ll x)
{
if(x<=MAX)return mu[x];//<n^2/3的
if(mm[x])return mm[x];//已算好的
ll ret=0;
int i=2,j;
while(i<=x&&i<2147483647)
{
j=x/(x/i);
ret+=(j-i+1)*Mu(x/i);//数论分块
i=j+1;
}
return mm[x]=1-ret;//记忆化
}
ll Phi(ll x)
{
if(x<=MAX)return phi[x];//<n^2/3的
if(pp[x])return pp[x];//已算好的
ll ret=0;
int i=2,j;
while(i<=x&&i<2147483647)
{
j=x/(x/i);
ret+=(j-i+1)*Phi(x/i);//数论分块
i=j+1;
}
return pp[x]=x*(x+1)/2-ret;//记忆化
}
```
### 3.数论分块 根据$\lfloor\frac{n}{i}\rfloor$最多只有$\sqrt{n}$种情况产生 可以化$O(n)$为O($\sqrt{n}$)
```cpp
while(i<=n)
{
j=min(n/(n/i),m/(m/i));
ans+=n/i*m/i*(sum[j]-sum[i-1]);//数论分块
i=j+1;
}
```
## 一般套路
先化简 然后通过交换求和次序 换元等 搞出两个积性函数的迪利克雷卷积形式 筛出这个函数的前缀和 通过数论分块解决