2023/09/08 upd：添加了总结。

数论总结

没活了。写点笔记。

本文md源码全长超过25KB、750行，除非有时间并不建议完整阅读而是通过Ctrl+F查找想阅读的部分

取模运算

定义。

在带余除法下，就是的余数。

整除性与约数

对于任意自然数，如果满足，那么称整除或是的约数，记作。反之记作。

。

根据约定，整除任意数。

最大公约数

定义两个数的最大公约数（Greatest Common Number）为最大满足的，记作。同时我们定义最小公倍数（Least Common Multiple）为最小满足的数，记作。

与之间的关系为。

一般而言，没有定义。

的性质包括等。

proof：对于任意，我们设，则，则；对应的，对于任意，。由于我们指定的是“任意”，所以。

求常用辗转相除法，即。

互质

定义互质当且仅当，记作。

一些常用性质：

扩展欧几里得算法

扩展欧几里得算法，简称exgcd，用于求解形如的二元一次整数不定方程，其精髓在于巧妙地运用辗转相除的性质通过构造递归解决问题。

我们先看一个更弱的问题：求的一组解。

首先当时，我们有，解得。

否则设是的解。

那么根据和取模运算的定义，我们得到。

把方程改写成相关，则。

此时我们就得到了一组解，即

我们发现这恰好是一个递归的问题，所以可以很轻易地编程解决。

由于辗转相除在（是 Fibonacci 数列）时取得最坏时间复杂度，而粗略估计与同阶，因此该算法时间复杂度为。

typedef std::array<int,2> pii;
inline pii exgcd(int a,int b){
    if(!b)return {1,0};
    pii x=exgcd(b,a%b);
    return {x[1],x[0]-a/b*x[1]};
    /*
    如果支持c++17可以这么写:
    auto [x,y]=exgcd(b,a%b);
    return {y,x-a/b*y};
    */
}

~~上面的写法比较非主流，下面是主流写法~~

inline void exgcd(int a,int b,int &x,int &y){
    if(!b)return void(x=1,y=0);
    exgcd(b,a%b,x,y);
    int t=x;x=y,y=t-a/b*x;
}

裴蜀定理

现在我们来解决更一般的原问题。

首先必定是的倍数，因此如果，那么无解；否则我们在两边同时乘，得到，即则是原方程的一组解。

同时，我们也得出方程有解的充要条件：。

上式就是裴蜀定理。

质数

定义一个正整数是质数（Prime），当且仅当满足下列条件：用语言描述即为：只能被和整除的大于等于的数是质数。一般而言不是质数。

前个质数为。

（若无特殊说明，下文均用代指质数，代指第个质数，代指质数集）

不是质数的数被称为合数。合数除了能被整除以外还有其他的约数。

质数是构成所有整数的基本元素。任意整数都能被表示为

常用结论

数最多存在一个大于的质因子。

合数一定存在一个介于的质因子。（利用这个结论可以判断质数）

证明显然。

唯一分解定理

有且仅有一种将数分解为若干质数乘积的方案。

proof：用归纳法。

时，显然只有唯一的分解方案。

否则设。

设，那么可以被唯一表示，而也可以被唯一表示，于是可以被唯一表示。

否则易证，但是由于，而唯一的数是，但是，于是矛盾。

证毕。

质因数分解

我们将数写作形如的形式，其中表示在的唯一分解中出现的次数。

这样写的好处在于有一些比较好的性质，如此外利用这一点，我们可以用唯一确定一个数。

利用常用结论，单次质因数分解的时间复杂度是的。

无穷质数定理

质数的个数是无限的。

proof：用反证法。

设是仅有的个质数，那么考虑数必定不能被整除（）。

那么要么本身是质数，要么还存在一个质数使得，都与是仅有的质数矛盾。

证毕。

Mersenne数

Mersenne数指形如的数。特别的，当时这个数也被称为Mersenne质数。

~~但是这个东西在 OI 中并没有什么卵用。~~

质数的密度

这里不加证明地给出或表示以内的质数个数。

基本筛法

如果我们要求出内的所有质数，就可以使用筛法。

倍数筛

我们将每一个数的所有倍数都标记为合数，剩下的就都是质数了。

运算次数约在左右，因此时间复杂度。

埃氏筛

倍数筛有大量的冗余标记，因为已经是合数的数的倍数会再次被标记。

我们考虑只用质数去标记合数，这样就可以大大减少冗余计算。

时间复杂度。

欧拉筛（线性筛）

埃氏筛仍然会出现冗余标记。更具体的，一个数会被它的每一种因子都标记一遍。我们希望每个数只被标记一次。

我们可以考虑每个数都只被其最小质因子标记一遍（因为一个数的最小质因子乘剩余部分可以唯一确定一个属），于是我们考虑存储每个数的最小质因子。

考虑枚举这个“剩余部分”。遍历到时，若，说明这个数是质数，把它加入到质数列表的末尾；然后对所有不大于的质数将标记为合数。

这样可以保证每个数只被它的最小质因子标记过，时间复杂度线性。

（实现时可能不会记录，而是和埃氏筛一样只记录标记。如果一个数没有被标记，说明是质数；从小到大枚举每个质数并打标记，如果枚举到的质数是当前的约数则说明下一个质数已经不是最小的质因子，停止枚举）

const int M=1e8;
std::vector<int> p;
int pt=0;
bool vis[M+5];
void getpr(){
    vis[1]=1;p.resize(1);
    for(int i=2;i<=M;++i){
        if(!vis[i])++pt,p.push_back(i);
        for(int j=1;j<=pt&&i*p[j]<=M;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}

阶乘

定义为的阶乘，记作。。

可以看出阶乘是以极快速度增长的。一般是时间复杂度能通过的最大数据范围。

我们可以在非常大的时候用斯特林公式估算：

阶乘的质因数分解

我们显然无法对阶乘的结果直接质因数分解。如果对阶乘的每一项都分别进行质因数分解的时间复杂度也是的，不是最优。

我们运用反演的思想，转而统计每个质因子的贡献。

如果我们将不同指数的质数分开计算，的出现次数是。证明显然。

因此每个质数的贡献是由于大于的取值都是，因此只需要统计项。

这样一来时间复杂度就降到。

常见函数

积性函数

如果函数满足对于有，那么称是一个积性函数。

欧拉函数

定义欧拉函数。

欧拉函数是一个积性函数。

proof：对于任意，都有（可用与质因数指数关系证明），那么就有种组合方式。

易证。

推论：。

proof： $函数的积性$

莫比乌斯函数

定义莫比乌斯函数莫比乌斯函数也是积性函数（简单分讨即可）。

莫比乌斯反演

常用结论：。

证明这玩意可以用二项式定理或迪利克雷卷积，限于篇幅不再赘述。

莫比乌斯反演的技巧在于抓住待求式中的等，将其化作等，然后改变枚举顺序以优化复杂度。此外还会经常遇到改枚举约数为倍数等技巧。

积性函数与线性筛

可以在筛内的质数的同时筛积性函数在范围内的所有数的取值。

以为例，我们考虑用 DP 的思想解决问题。证明可结合前文提到的计算公式。

同余

（本节中不代指质数，只代指模数）

定义在模下同余，当且仅当，记作。

OI 中为了避免精度问题，大部分计数题都会要求输出答案对某个模数（通常是或）取余的结果，相当于在模意义下进行同余运算。

基本性质

加减乘运算在同余运算中不受影响，换言之但是除法运算并没有这些性质，譬如但是。

因此如果涉及除法运算，我们需要引入乘法逆元。

乘法逆元

定义是在模意义下的乘法逆元当且仅当，的乘法逆元记作。

容易发现是在模意义下的乘法逆元的同时，也是在模意义下的乘法逆元。而如果则称是单位元。一般而言乘法逆元单位元都为。

引入乘法逆元之后，我们就可以将转化为进行除法了。

下文“逆元”均指代乘法逆元。

exgcd的同余形式

exgcd也可以用于求解一元一次同余方程：相当于求解中的。

proof:将移到左边，即得到，由于，得到。

用exgcd求解逆元

我们发现实质上就是要求解，即。直接解方程即可。

int inv(int a,int p){
    int x,y;
    exgcd(a,p,x,y);
    return (x%p+p)%p;//防止出现负数
}

逆元的存在性

根据裴蜀定理，此方程有解当且仅当。因此在模意义下有逆元当且仅当。

费马小定理

对于质数，若，那么 proof:

考虑在模意义下必定是一个的排列（由于，那么与不可能在模意义下同余，进而推出），那么又因为得到。

由于是质数，则，那么两边同时乘，得到。

证毕。

费马小定理求逆元

是质数时可以用费马小定理求逆元。

由于则一定存在，那么在两边同时乘，得到。

那么我们就可以使用快速幂求出即在模下的逆元。时间复杂度。

补充：费马小定理的另一种证明

数形结合。

我们建一张图，结点为，从向连边。

那么根据抽屉原理，我们从任何一个数出发，在绕步之后必定会绕到之前走过的点，也就是说一定会绕到一个环上。

由于是质数而的所有数都和互质，所以每个数都存在唯一逆元，因此每个点入度为。

这也就说明了这个图是由环构成的。我们接下来需要证明环的长度为的约数。

我们设所在的环长为。首先如果得证；否则设不在所在的环上，所在的环长为。

那么我们可以推出两条限制：

所在环上的所有数都不在所在环上。
所在环上的每个数与上每个数同余且一一对应（比如在出发走三步再与从出发走三步结果一样，即乘法交换律）。

因此我们推出所有环环长必须相等。

再加之每个数一定在一个环上（否则可以一直连边直到回来），因此环长必定是的约数，也就是说从任意数开始走步必定回到起点。

证毕。

威尔逊定理

。

proof：求解方程，则，即由于是质数时的所有数都能一一配成一对逆元，于是对不是质数的数大力分讨一下即可。

中国剩余定理

中国剩余定理（Chinese Remainder Theorem，CRT）是一种用于求解线性同余方程组的算法。

由于~~阉割版~~原版CRT较为难以理解，下文将仅介绍与原版CRT除了名字没有一分钱关系的exCRT算法。它更短、适用范围更广且更加容易理解。如果您想了解原版CRT请左转OI-Wiki。

求下列方程的最小解（或模的值）： 不保证模数两两互质。

我们首先把这一项化为。

把方程写作二元一次不定方程的形式：显然若则无解，否则将这个方程两边同时除以得到然后直接解即可。

exCRT的核心思想是归纳，即考虑如何利用前项的答案和第项算出第项的答案。

因此我们只需要考虑只有两项的情况。我们假设要解这个方程：设，那么如果此方程有解，我们就得到了满足这两个方程的，合并为最终合并得到方程即为答案。

时间复杂度。

欧拉定理与拓展欧拉定理

欧拉定理

欧拉定理本质上是费马小定理的拓展。

欧拉定理：如果，那么。

证明：仍然考虑用建图的方式理解。

由于，则均，因此从出发也一定是一个环。

由于互质等价于有逆元，那么在模意义下有种取值。

然后和费马小定理的证明一样的讨论就好了。

必成倍数性质

若的质因子都是的质因子，则，。其中。

分解质因数后证明显然。

扩展欧拉定理

proof：

将分为，使得与互质，的质因子都是的质因子。

那么有。

根据欧拉定理，。

而根据前文所述的必成倍数性质，。

CRT 合并即可。

拓展欧拉定理一般用于求解大指数幂。

乘法逆元的其他求法

线性求逆元

~~我从来不用~~

存在线性求出内所有数逆元的算法。 proof大概是把写成关于的带余除法式。

线性求个数的逆元

我们可以在的时间复杂度内求出任意个与模数互质的数的乘法逆元。

设序列为。

设，，。

我们可以用线性时间求上面的三个量，然后用的时间求出。

由于于是我们就有。

离散对数问题

求解：

BSGS

大步小步（Baby Step Giant Step,BSGS）算法是一个能在时间内求解离散对数问题的算法，其本质是根号平衡、双向搜索。

首先解决质数的情况。根据欧拉定理，如果有解一定存在在范围内。

我们设，其中，则，即

我们可以将所有的放到一个数据结构里，然后枚举，每次在这个数据结构中查找是否存在，如果存在且对应的满足则答案就是；如果最后都没有找到则无解。

我们发现这个数据结构需要插入和查询一个数是否存在，哈希表完美契合这个需求，这两种操作都是的。

最终时间复杂度。

exBSES

接下来我们解决不是质数的情况。

当不是质数时在模意义下可能不存在逆元，因此我们无法直接使用 BSGS。

考虑把原式改写成 exgcd 的形式：

当时，原方程无解；否则我们在等式两边同时除以，得到

此时相当于要求解子问题

如果此时则直接调用 BSGS 即可；否则重复此过程直到。

最终答案要加上减小的次数。至此问题解决。

根据必成倍数性质，最多会减小次，因此时间复杂度。

质数检测与质因数分解的加速

朴素的质数检测是的、质因数分解是的，在一些情境下可能不够快。

这一节介绍两种算法用于加速质数检测和质因数分解。

Miller-Rabin 质数检测

Miller-Rabin（下文简称 MR）是一个质数检测算法，可以做到的时间复杂度，其中是运行检测的次数。

二次探查定理

proof：，因为是质数，则与中必有一个是的倍数。

算法流程

我们基于两个逆否命题：

费马小定理的逆否命题：（记为条件一）
二次探查定理的逆否命题：（记为条件二）

我们重复以下步骤轮，若每轮检测都通过则认为是质数：

设（其中是奇数），并选取底数。
若，终止检测并返回不通过。（条件一）
我们枚举，若，终止检测并返回不通过。（条件二）
- 优化：若，则后续的的结果均为，直接返回通过检测。

底数选取技巧

对于 int 类型的整数，我们进行次检测，选取前个质数作为底数。
对于 long long 类型的整数，我们进行次检测，选取前个质数作为底数。

这样选取可以保证最终结果绝对正确（详见OEIS A014233）。

不过需要注意，质数无法通过以它本身为底数的检测，因此需要特判。

Pollard-Rho

Pollard-Rho 算法是一种基于随机的高效的质因数分解算法，可在期望时间复杂度时间内求一个数的任意一个因子。（事实上在找到第一个因子之后找到下一个的时间将大大减少，因此质因数分解的时间复杂度也是）

生日悖论

在随机生成数，那么期望在第次就会出现两个相同的数。

思想

首先调用 MR 判断待分解的数是否是质数。如果不是，设，那么我们可以不断在内生成随机数，期望在次生成后生成的数中存在使，进而，于是就成为了的因子，递归到和的子问题。

设，则，那么期望步就能生成这样的一对。

流程

现在我们考虑如何快速判断某个生成的数与之前出现过的数同余。

我们选取任意一个函数并以递推式生成序列。

此时我们设想一下在序列的虚拟建图（）中有两个“” 形：

大：由于的值只与有关，那么一旦重复就会进入循环，这个过程类似一个 "" 形。
小：同理，的值也一定是一个形。

根据生日悖论，如果选取恰当，那么大的长度期望为，小的长度期望为。

形过程的性质：若，则，有。

我们使用弗洛伊德判环法：我们使用两个指针，每次先让跳两步然后让跳一步。

如果，说明在小上追上了。

如果此时，说明与此同时在大上也追上了，接下来无论怎么追结果都是一样，放弃现有的并重新生成。
否则我们就找到了满足条件的两个数，退出循环。

这种判环法最坏会执行小长度步，因此找到一对期望时间复杂度。

总结

数论作为 OI 中最考验思维的部分之一，其灵活性和复杂程度导致了它成为了许多思维能力不好的选手（包括我）一座绕不去的大山。

这次写笔记虽然花了不少时间，但是写完之后去练题还是实打实感受到了自己思维的提升，对一些新手期只能背板子的算法的理解也加深了不少。

数论由于较为繁杂，大量刷题反而提升不大，练多不如练精，做数论题一定要多思考，对于特别重要的思维模型（如转化为 exgcd 是许多算法的基础）要予以积累。

虽然 OI 不考证明，但是数论的证明过程中往往蕴含在整个 OI 中都非常重要的思想（如 exgcd 和 exBSGS 的递归思想，exCRT 中的归纳思想，阶乘分解质因数中的反演思想，BSGS 的根号分治与双向搜索思想，），因此数论的证明应当尽量理解，对思维也有启发意义。

部分参考资料

《具体数学》，Graham、Knuth、Patashnik著
OI-Wiki