编程中的较高端的数论知识总结1--莫比乌斯反演

前言

之前写过一篇名叫基础数论总结的博客，自己认为写得不是很好，当时刚开始用CSDN写博客，$\LaTeX$公式写得不是很熟练，花了快$3$个月才写完，而且写得比较杂，有的地方也写得不够全，后来也没去改过
这次疫情期间，学校老师让我写一篇数论总结的博客，让我回学校后和其他同学分享，于是就有了这一系列博客
对于以前那篇，如果有不懂的可以自行在百度上查询，我也不会再去更改了因为懒

一些需要使用到的数论知识

简单的知识

在我的另一篇博客中已经有了，这里就不再赘述

简化的if语句

在数论中，我们常常使用$[P]$来表示一个命题的正误
如果$P$是一个真命题，那么$[P]$的值就是$1$，反之，如果是假命题，值就是$0$
其实就相当于：

if(P) [P]=1;
else [P]=0;

数论函数

概念

数论函数指定义域为正整数的函数，每个数论函数都可视为复数的序列——度娘（有删改）

积性函数

在数论函数中，最重要的性质就是积性，虽然我前面那篇博客已经写过了，但是因为太重要了，我还是要在写一遍
积性函数一共分为两类

（普通的）积性函数

对于所有的积性函数，都满足一个性质：$\forall a,b\in \Z^+且gcd(a,b)=1,则f(ab)=f(a)f(b)$
例如，欧拉函数$\varphi(n)$就是一个典型的积性函数

完全积性函数

某些特殊的积性函数会满足：$\forall a,b\in \Z^+,则f(ab)=f(a)f(b)$，我们把这些函数叫做完全积性函数
最明显的完全积性函数就是$id(n)=n$，这显然是一个完全积性函数

常见数论函数

首先，是三个完全积性函数：

1. $\epsilon(n)=[n==1]$（单位元）
2. $I(n)=1$
3. $id(n)=n$

emmm……其实后面两个啥用都没有
接着，是一些常见的积性函数

1. $\varphi (n)=n \times \prod \limits_{质数p|n}\left(1-\frac{1}{p}\right)$（欧拉函数）
2. $\mu (n)=\begin{cases}(-1)^t n无平方因子，质因数个数为t\\0 n有平方因子\end{cases}$（莫比乌斯函数，后面讲莫比乌斯反演时有用）
3. $\tau(n)=\sum \limits_{d|n}1$（正因子个数）
4. $\sigma(n)=\sum \limits_{d|n}d$（正因子和）

不是积性函数的数论函数好像没有几个会考的，所以我也不列举了其实我也不知道

莫比乌斯反演

小小的计算

在讲述这个看似高级的东西之前，我们做一个小小的计算
我们假设有两个数论函数$f(n)$和$F(n)$，满足$F(n)=\sum \limits_{d|n}f(d)$
那么，我们来枚举一下前几项
$F(1)=f(1),F(2)=f(1)+f(2),F(3)=f(1)+f(3),F(4)=f(1)+f(2)+f(4),F(5)=f(1)+f(5)$
$F(6)=f(1)+f(2)+f(3)+f(6),F(7)=f(1)+f(7),F(8)=f(1)+f(2)+f(4)+f(8),F(9)=f(1)+f(3)+f(9)$
接着，我们来尝试着倒过来表示，枚举一下前几项
$f(1)=F(1),f(2)=F(2)-F(1),f(3)=F(3)-F(1),f(4)=F(4)-F(2),f(5)=F(5)-F(1)$
$f(6)=F(6)-F(3)-F(2)+F(1),f(7)=F(7)-F(1),f(8)=F(8)-F(4),f(9)=F(9)-F(3)$
我们来从中寻找一下规律，用$f(n)=\sum \limits_{d|n}g(d)F\left(\frac{n}{d}\right)$表示
问题是，$f(d)$究竟是多少呢？
我们来求一下：
$g(1)=1,g(2)=-1,g(3)=-1,g(4)=0,g(5)=-1,g(6)=1,g(7)=-1,g(8)=0,g(9)=0$
好像有平方因子的都是$0$，但是无平方因子的呢？好像都是$1$和$-1$，但是什么时候是$1$，什么时候又是$-1$呢？
通过观察，我们可以发现：$g(n)=(-1)^t$，$t$为$n$的质因子个数！
因此这个函数可以表示为：
$g(n)=\begin{cases}(-1)^t n无平方因子，质因数个数为t\\0 n有平方因子\end{cases}$
我们把这个函数成为莫比乌斯函数，用$\mu(n)$来表示
那么，我们得出来一个漂亮的式子：$f(n)=\sum \limits_{d|n}\mu(d)F\left(\frac{n}{d}\right)$
话说我们不是要讲高端的莫比乌斯反演吗，怎么讲了这么多废话？
这就是莫比乌斯反演啊！我们不知不觉的已经讲完了，是不是一点都不难呢？
其实，莫比乌斯反演的本质就是一个容斥，所以在做题时，我们可以先做出这个容斥，然后再考虑如何使用莫比乌斯反演

莫比乌斯函数

接下来，我们来具体讲解一下莫比乌斯反演中的一个重要元素——莫比乌斯函数

性质

莫比乌斯函数有几个简单的性质，大家可以了解一下
①$\sum \limits_{d|n}\mu(d)=\begin{cases}1 (n=1)\\0 (n>1)\end{cases}$
证明：当$n=1$时，$\sum \limits_{d|n}\mu(d)=\mu(1)=1$（显然）
   当$n>1$时，设$n=\prod\limits_{i=1}^{k}p_i^{\alpha_i}$
       又$\because n$中质因子个数为$t$的因子只有$\binom{k}{r}$个
        $\therefore \sum \limits_{d|n}\mu(d)=\sum \limits_{i=0}^{k} (-1)^i\binom{k}{i}=(1-1)^k=0$
注：倒数第二步用到了二项式定理，在我的另一篇讲解组合计数的博客中有写到（该博客目前还未完成，不会的自行百度）
②$\sum \limits_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(d)}{d}$
证明：令$F(n)=n,f(n)=\varphi(n)$
$\therefore F(n)=\sum \limits_{d|n}f(d)$（显然，不会的话自己思考一下）
$\therefore f(n)=\sum \limits_{d|n}\mu(d)F\left(\frac{n}{d}\right)$
$\therefore \sum \limits_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(d)}{d}$
③$\mu(n)$为积性函数
证明：设$n=\prod\limits_{i=1}^{k}p_i^{\alpha_i},m=\prod\limits_{i=1}^{t}q_i^{\beta_i}$
$\therefore$若$\exists \alpha_i>1$或$\beta_i>1$，则$\mu(mn)=0=\mu(m)\mu(n)$
 否则，$\mu(mn)=(-1)^{k+t}=(-1)^k(-1)^t=\mu(m)\mu(n)$

计算方法

讲了这么多，我还是不知道莫比乌斯反演怎么求啊！
别着急，我这就讲
因为莫比乌斯函数是积性函数，我们可以使用线性筛来求解
线性筛大家应该都知道吧？我们在求解欧拉函数时就使用了这个方法，因为欧拉函数也是积性函数
具体代码如下：

int MU(){
    for(int i=2;i<=MAXN;i++){
        if(!v[i]) p[++s]=i,mu[i]=-1;
        for(int j=1;j<=s&&i*p[j]<=MAXN;j++){
            v[i*p[j]]=1;
            if(i%p[j]) mu[i*p[j]]=-mu[i];
            else{mu[i*p[j]]=0;break;}
        }
    }
}

在我的github仓库中，有这些模板代码，大家可以自己去拷贝

莫比乌斯反演的严格证明

我们之前是用找规律的手法推出莫比乌斯反演的，那我们可不可以严格的证明呢？
显然是可以的，下面是证明过程：
$\because \sum \limits_{d|n}\mu(d)F\left(\frac{n}{d}\right)=\sum \limits_{d|n}\mu(d)\sum \limits_{i|\frac{n}{d}}f(i)=\sum \limits_{i|n}f(i)\sum \limits_{d|\frac{n}{i}}\mu(d)$
$\therefore$根据莫比乌斯函数的性质①，可知$\sum \limits_{d|\frac{n}{i}}\mu(d)=[i==n]$
$\therefore \sum \limits_{d|n}\mu(d)F\left(\frac{n}{d}\right)=\sum \limits_{i|n}f(i)\sum \limits_{d|\frac{n}{i}}\mu(d)=\sum \limits_{i|n}f(i)[i==n]=f(n)$
这就是莫比乌斯反演证明的全过程了，只有$3$行，但信息量很大，请大家好好消化这段证明过程

例题

如果你已经掌握了上面的所有内容，那么恭喜你，你已经学完了莫比乌斯反演的全部内容了，剩下的就是实际练习了
在这里，我只详细写一道例题的题解，剩下的请大家自行完成（也可能会另外发题解在其他文章中）

[HAOI2011]Problem b

这是一道最最经典的莫比乌斯反演的题目，基本上每篇有例题的讲莫比乌斯反演的博客都会讲这道题

题目

题目描述

对于给出的$n$个询问，每次求有多少个数对$(x,y)$，满足$a \leqslant x \leqslant b$，$c \leqslant y \leqslant d$，且$\gcd(x,y) = k$，$\gcd(x,y)$函数为$x$和$y$的最大公约数

输入格式

第一行一个整数$n$，接下来$n$行每行五个整数，分别表示$a,b,c,d,k$

输出格式

共$n$行，每行一个整数表示满足要求的数对$(x,y)$的个数

输入输出样例

输入

2
2 5 1 5 1
1 5 1 5 2

输出

14
3

说明/提示

对于$100\%$的数据满足：$1 \leqslant n,k \leqslant 5 \times 10^4$，$1 \leqslant a \leqslant b \leqslant 5 \times 10^4$，$1 \leqslant c \leqslant d \leqslant 5 \times 10^4$

题解

算法1（20分）

我们先不要考虑什么莫比乌斯反演之类的高级东西，先从简单出发，一步步深入，最终A掉这些题
这也是初学莫比乌斯反演，乃至学习新的数论算法的一个重要方法
你能想到的最最最暴力的方法是什么？当然是枚举啦！
枚举$[a,b]$之间的$x$和$[c,d]$之间的$y$，判断$gcd(x,y)$是否等于$k$就完事了
能不能稍微优化一下呢？当然可以！
我们枚举$\left[\lceil\frac{a}{k}\rceil,\lfloor\frac{b}{k}\rfloor\right]$之间的$x’$和$\left[\lceil\frac{c}{k}\rceil,\lfloor\frac{d}{k}\rfloor\right]$之间的$y’$，判断$gcd(x’,y’)$是否等于$1$即可，效率为$\Theta\left(T\frac{nmlog\frac{n}{k}}{k^2}\right)$

算法2（50分）

设$Ans_{n,m}$为$a=1,b=n,c=1,d=m$的情况下的答案
那么，这道题的答案就是$Ans_{b,d}-Ans_{a-1d}-Ans_{b,c-1}+Ans_{a-1,c-1}$了
那如何优化计算$Ans_{n,m}$呢？
首先，可以采用和算法一一样的方法，转化为求$\sum \limits_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum \limits_{y=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(x,y)==1]$
接着，我们假设$f_x=\sum \limits_{y=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(x,y)==1]$，那么，$Ans_{n,m}=\sum \limits_{x=1}^{\lfloor\frac{n}{k}\rfloor} f_x$
所以，我们只需要求出$f_x$就可以了
设$x=\prod \limits_{i=1}^{k}p_i^{\alpha_i}$
那么，$f(x)=\lfloor\frac{m}{k}\rfloor+\sum\limits_{j=1}^{k}(-1)^{j}\sum\limits_{1\leqslant i_11000$，所以$k<=4$，所以可以得50分

算法3（还是50分）

假设$f_k=\sum \limits_{x=1}^{n}\sum \limits_{y=1}^{m}[gcd(x,y)==k],g_k=\sum \limits_{x=1}^{n}\sum \limits_{y=1}^{m}[k|gcd(x,y)]$
那么，我们可以轻松地得出：$g_k=\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}f_{kd}=\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor$
所以，我们就可以得到：$f_{ki}=g_{ki}-\sum\limits_{j=1}^{\lfloor\frac{n}{k}\rfloor}f_{kij}$
时间复杂度为$\Theta\left(T\frac{n}{k}log\left(\frac{n}{k}\right)\right)$

算法4（70分）

接下来，我们就要真正使用到莫比乌斯反演了
因为$g_k=\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}f_{kd}$，所以$f_k=\sum \limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu_dg_{kd}=\sum \limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu_d\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$
使用线性筛预处理$\mu_d$，复杂度为$\Theta\left(n+T\frac{n}{k}\right)$

算法5（100分）

看到$\lfloor\frac{n}{kd}\rfloor$这种式子，大家应该都能反应过来要使用数论分块进行计算
以计算$\sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$为例，讲解数论分块算法
枚举每一个$\lfloor\frac{n}{d}\rfloor$和$\lfloor\frac{m}{d}\rfloor$都分别相等的块，假设开始位置为$i$，那么结束位置$j=min\left(\left\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor,\left\lfloor\frac{m}{\lfloor\frac{m}{i}\rfloor}\right\rfloor\right)$
这样的话，复杂度就是$\Theta(n+T(\sqrt{n}+\sqrt{m}))$
正解代码：

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int a,b,c,d,k,mu[50010],v[50010],sum[50010];
long long fk(int x,int y)//数论分块
{
    if(x>y) swap(x,y);
    long long ans=0;
    for(int i=1,j;i<=x;i=j+1){
        j=min(x/(x/i),y/(y/i));
        ans+=(long long)(sum[j]-sum[i-1])*(x/i)*(y/i);
    }
    return ans;
}
int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=50000;i++) mu[i]=1,v[i]=0;
    for(int i=2;i<=50000;i++){
        if(v[i]) continue;
        mu[i]=-1;
        for(int j=2*i;j<=50000;j+=i){
            v[j]=1;
            if((j/i)%i==0) mu[j]=0;
            else mu[j]*=-1;
        }
    }//计算mu_d
    sum[0]=0;
    for(int i=1;i<=50000;i++) sum[i]=sum[i-1]+mu[i];
    while(T--){
        cin>>a>>b>>c>>d>>k;
        cout<<fk(b/k,d/k)-fk(b/k,(c-1)/k)-fk((a-1)/k,d/k)+fk((a-1)/k,(c-1)/k)<<endl;
    }
}

题目推荐

1. 洛谷P2257 YY的GCD
2. 洛谷P4449 于神之怒
3. 洛谷P1829 Crash的数字表格/JZPTAB
4. 洛谷P3312 数表
5. 洛谷P3327 约数个数和

   参考资料

6. WC2016中山纪念中学宋新波莫比乌斯反演PPT
7. PoPoQQQ的莫比乌斯反演PPT

相关文章：

1. 编程中的较高端的数论知识总结2——狄利克雷卷积