姓名： 陶荣杰
赛道： 提高组
类型： 算法技能
~~~~~~~~~~~~~~~~~~~~~~~~~ 莫比乌斯反演
前置知识：狄利克雷卷积，数论分块
- 莫比乌斯函数
~~~~ 定义 \mu 为莫比乌斯函数，定义为
\mu(n)=
\begin{cases}
0~~~~~~~~~~~~~n=1\\
1~~~~~~~~~~~~~n含有平方因子\\
(-1)^k~~~~~k为n不同质因子个数
\end{cases}
\tag{1}
- 性质
\sum_{d|n}\mu(d)=
\begin{cases}
1 ~~~~n=1\\
0 ~~~~n\not=1
\end{cases}
~~~~~~~ 不难看出左边是 \mu 与 1 的狄利克雷卷积，而右边是元函数 \varepsilon ,所以 \mu * 1=\varepsilon
- 补充结论
~~~~ 1.反演结论 [gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)\tag{2}
~~~~~~ 证明：
[gcd(i,j)=1]=\varepsilon(gcd(i,j))= \\
(\mu * 1)(gcd(i,j))=\\
\sum_{d|gcd(i,j)}\mu(d)
~~~~ 2. \varphi(n)
\varphi(n)=\sum_{d|n}d\mu(\frac{n}{d}) \tag{3}
~~~~~~ 证明：
~~~ 学过狄利克雷卷积的人应该都知道（雾,有这么一个结论
\varphi*1=id
~~~ 我们不妨对左右两边同时卷 \mu 可得
\because~\varphi*1*\mu=id*\mu\\
\therefore~\varphi*(1*\mu)=id*\mu\\
\therefore~\varphi*\varepsilon=id*\mu\\
\therefore~\varphi=id*\mu\\
\therefore~ \varphi(n)=\sum_{d|n}id(d)\mu(\frac{n}{d})=
\sum_{d|n}d\mu(\frac{n}{d})\\
（注意:此证明方法会在后面证明莫比乌斯反演用到）
- 莫比乌斯函数与线性筛
~~~~ 由于 \mu 是积性函数，我们可以根据他的性质用线性筛求出莫比乌斯函数
void Muelsyse(){
vis[1]=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]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
- 莫比乌斯变换（ and 反演）
~~~~ 设 f(n),g(n) 是两个数论函数。
~~~~ 形式一：如果 f(n)=\sum\limits_{d|n}g(d), 那么 g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})。
~~~~ 形式二：如果 f(n)=\sum\limits_{n|d}g(d), 那么 g(n)=\sum\limits_{n|d}\mu(\frac{d}{n})f(d)。
这种形式下，数论函数 f(n) 称为数论函数 g(n) 的莫比乌斯变换，数论函数 g(n) 称为数论函数 f(n) 的莫比乌斯逆变换（反演）。
容易看出，数论函数 g(n) 的莫比乌斯变换，就是将数论函数 g(n) 与常数函数 1 进行狄利克雷卷积。
~~~~~~ 证明：(运用狄利克雷卷积)
~~~~~ 原命题:已知 f=g*1, 求证 g=f*\mu
~~~~~ 对 f=g*1 左右两边同时卷 \mu
g*1*\mu=f*\mu\\
g*(1*\mu)=f*\mu\\
g*\varepsilon=f*\mu\\
g=f*\mu
- 例题
求
\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==k]的值
先改变枚举上限
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)==1]
使用反演结论
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)
改变求和顺序先枚举 {d|gcd(i,j)}
\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j]
我们知道 1 ~ \lfloor\frac{n}{k}\rfloor 中 d 的倍数有 \lfloor\frac{\lfloor\frac{n}{k}\rfloor}{d}\rfloor 个,也就是 \lfloor\frac{n}{kd}\rfloor 个 原式便能转换为
\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor
显然使用数论分块
~~~~ more题:
~~~~ Crash的数字表格 / JZPTAB
~~~~ [HAOI2011] Problem b
特别感谢：@潘建希
喜欢的记得点个赞，Ciallo～(∠・ω< )⌒☆
