基础数论学习笔记

基础数论学习笔记
CHANGE LOG
- 2021.12.6. 重构文章，删去线性筛部分，修改部分表述。
- 2022.3.15 二次重构文章。
- 2022.3.23 三次重构文章。
- 2022.3.24 重构完成，新增威尔逊定理，素数在阶乘和组合数中的幂次，阶与原根，高次剩余和卢卡斯定理。
0. 前置知识

0.1 基本定义与记号

Abstractness is the price of generality.

读者需要知道一些数论相关的基本概念，如同余符号及其含义，最大公约数，并掌握基本数论算法如快速幂，辗转相除法求解。
- 整除：若非零整数是整数的因数即，则称整除或被整除，记作。若反之则称不能整除或不能被整除，记作。
- 同余：表示整数和模正整数的余数相等。
- 最大公约数：整数和的最大公约数是最大的整数使得整除且整除，记作。在不引起歧义的前提下有时会简写为。
- 互质：若整数满足，则称互质，记作。一般均为非负整数。注意，，和任何整数互质。
- 表示素数集。
- 剩余类：模同余的所有数构成的等价类被称为模的剩余类。它们等价，因为我们在模意义下讨论它们。模余的剩余类记作。容易发现模的剩余类共个。
- 完全剩余系：从个模剩余类中各选一个数，它们构成模的完全剩余系。
- 简化剩余系：从与互质的剩余类中各选一个数，它们构成模的简化剩余系。读者在接下来的章节中将了解到，等于。简化剩余系又称为 既约剩余系 或缩系。
- 乘法逆元：若，则称为在模意义下的乘法逆元，记作。
- 质因子次数：当中质因子的次数记作。即且。严格意义上应记为（希腊字母 nu）。为方便，本文暂记为。
- 各位数字之和：在进制下的各位数字之和记作。
0.2 费马小定理

当是质数时，其因子只有和两个。因此，若两个数相乘是的倍数，其中必然至少有一个是的倍数。

当不是的倍数时，不存在且使得，因为这需要是的倍数，与的限制矛盾。

考虑的所有数，它们乘以之后在模意义下互不相同，说明仍然得到的所有数。

因此，，即

上述结论称为 费马小定理。根据推导过程，它适用于是质数且不是的倍数的情形。

0.3 模意义下乘法逆元

根据费马小定理，当为质数时，

据此可快速幂求出一个数在模质数意义下的乘法逆元。

当非质数时，有乘法逆元的充要条件为。我们将在第一章展开讨论。

给出一些模质数意义下求乘法逆元的常见技巧。
1. 线性求逆元：考虑 增量法。假设的逆元已知。设，即和分别是对做带余除法的商和余数。因为，两边同时除以，得。时间复杂度线性。
2. 线性求任意个数的逆元：设为的前缀积。算出后通过得到前缀积的逆元，则。时间复杂度。
0.4 威尔逊定理

由于乘法逆元成对出现，这启发我们思考，所有数能否两两配对互为逆元？若可以，那么说明当是质数时，。

可以，但不完全可以，因为和的逆元均为它本身，且仅有这两个数满足。这符合我们的直观认知，毕竟在实数域下有且仅有解。

证明：求解方程。移项，使用平方差公式，。显然，为使等式左端等于，必然有。证毕。

因此，我们需要对结论进行一些修正，即当是质数时，。特殊考虑，发现符合该结论。

既然有了充分条件，我们自然会考虑不是质数的情况。
1. 当为完全平方数时，考虑和。它们相乘后模等于。因此，若即为大于的完全平方数时，。
2. 当时，。
3. 当为大于的非完全平方数时，令为的最小质因子，则，故。
综上，我们得到了 威尔逊定理：与是质数等价。

我们尝试将威尔逊定理扩展至素数的幂的情形，即考虑以内所有与互质的数的乘积模，记为。

仍然考虑求解即求出逆元为本身的数，并将非的其它所有数与其逆元两两配对（因为我们只考虑与互质的数，所以其在模意义下显然存在逆元），这说明我们只需考虑所有的乘积。

因式分解得到。

注意到当时，和不可能均是的倍数，因此必然有或。这和一般情况等价，因此仍然有。

当时，和可能同时为的倍数，但不可能同时为的倍数。因此，若和同时为的倍数，除掉不能被整除的那个数的质因子，得到或。这说明当时方程有四个解和。注意，当时四个根均重合，此时；当时两对根重合，此时。否则。

综合上述两种情况，我们得到如下推论

在 exLucas 中用到了该结论。

0.5 素数在阶乘中的幂次

给定正整数和质数，求。

我们考虑将当中所有的倍数提出来，然后全部除以。这一步消掉的质因子个数为，因为当中的倍数有个。

上一步操作后，我们得到了。我们将其中所有的倍数提出来，然后全部除以。这一步消掉的质因子个数为。

以此类推，直到。此时已经没有的倍数了。

因此，我们有如下结论：
- 这一定理由勒让德（Legendre）在 1808 年提出。
考虑换一种方法求和。我们尝试对在进制下的每一位，求出它对每次提出因子个数的贡献之和。不妨设，则

通过上述推导，我们得到了的另一种表示方法。

特别地，当时，。

0.6 素数在组合数中的幂次

根据 0.5 节的结论以及组合数公式，我们有

考虑和 在进制 下相加得到的过程，其中是质数。每产生一次进位，各位数字之和就会减少，因此在组合数中的幂次即进制下加上需要进位的次数，也等于减去需要借位的次数。

上述结论被称为 Kummer 定理，在 Lucas 定理中有用。

0.7 其它有用的事实

因为这个结论非常经典且容易理解，但证明较繁琐，故写在此处。

在一个长为的环上每一步走条边，形成的子环个数为且环长为。

感性理解：给环编号，走到的点的编号模一定相同，且可以证明一定能走到所有编号模相同的点。

证明：令，按顺序为环上的每个点标号，即。从开始每一步走条边，到达的点必然与在模意义下同余，因为均为的倍数，为加上之后对取余并不影响。

首先证明一个引理：当时，从环上任意一个节点出发，能够走遍所有点。

证明：不妨设从点开始，则走步后到达的节点编号即。欲证原结论，只需证明对于任意，均有，即走步到达的节点互不相同。

考虑反证法，假设存在，移项得到。因为，所以，这与矛盾。得证。

通过上述推导过程我们也可以看出，反证法在证明两个数不相等时非常有用。

不妨设。考虑当中所有模余的数，将其重标号为，形成一个长为的子环。因为，所以。根据引理，在这个长为的子环上每一步走条边（相当于在原环上走条边），能够走遍子环上每一个点。

因此形成的子环长为即，且每一个模的剩余系均恰好形成一个子环，因此子环个数为，即。或者说，子环长乘以子环个数等于环长，因为每个模的剩余系即每一个子环是等价的，均为在内模相同的所有数，只是子环之间在原环上的标号模不同。证毕

相关应用见 P5582 [SWTR-01] Escape，P5887 Ringed Genesis，P6187 [NOI Online #1 提高组] 最小环。

1. 扩展欧几里得算法

扩展欧几里得算法简称扩欧或 exgcd。它是求解最大公约数的欧几里得算法的扩展，用于求解形如的二元线性不定方程。

我们将看到扩展欧几里得算法与最大公约数的联系。

1.1 解的存在性

在求解形如的不定方程之前，我们首先需要知道如何判定它有解。
- 在求解方程之前，首先需要判断解的存在性。
先考虑一些较弱的结论。容易发现，无论的取值，左式一定是的倍数。因此，当时，方程显然无解。这使得我们可以为方程两侧同时除以。

同时，我们注意到为和同时除以之后，互质。这说明我们将问题简化为求解互质时的情形。可见优先判断解的存在性的重要性。

根据直观感受，对于，似乎能组合成任意一个整数，因为它们没有共同质因子。显然，这只需证明可以取到当中的任何一个数。

证明是容易的，因为提供了很强的性质。注意到这实际上是将费马小定理的证明中，为质数的条件去掉了，换成了，本质并没有差别。

考虑和满足且，则。若存在，则。因为，所以（能够约去的原因是它不提供任何含有的质因子，也就是对使得成立没有任何 “贡献”），这与的限制矛盾。证毕。

因为在时取遍所有整数，所以若，方程就一定有解。

综合上述结论，我们得到了判断二元线性不定方程存在解的 充要条件：。这被称为 裴蜀定理 或 贝祖定理。

1.2 算法介绍

欲求解，设，我们只需求解，并将解乘以。根据裴蜀定理，方程的解必然存在。

注意到等式右端等于前系数的最大公约数。回顾欧几里得算法（即辗转相除法），我们用到了关键结论，将问题缩至更小的规模上。利用这一思想，我们尝试将求解的方程也缩至更小的规模上。

考虑 递归构造。假设我们已经得到了的一组解，则

对比等式两端，有，，递归计算即可。递归边界即当时，根据辗转相除法，，故此时，即为一组解。

上述过程即扩展欧几里得算法，时间复杂度是辗转相除法的。代码如下。
cpp
```
void exgcd(int a, int b, int &x, int &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
```
注意，扩欧求得的解为的一组特解。为求得原方程的一组特解，还需将乘以。

1.3 解的形式与数值范围

显然，不定方程若存在解，则存在无穷解。我们需要通解的表示形式。

扩欧可以求得一组特解。根据，设，那么，故。因此是的倍数，同理。故通解形如

特解的数值范围详见 ycx 的博客关于 exgcd 求得特解的数值范围。这里仅给出结论：对于非平凡情况，有且。平凡情况：或。

1.4 应用
1. exgcd 的重要应用是求解一元线性同余方程。只需将其看成二元不定方程并使用 exgcd 求解即可。
2. 当模数不是质数时，费马小定理不再适用，但模意义下的乘法逆元仍可能存在。在模意义下存在逆元当且仅当，因为求逆元相当于求解即使得成立的。根据裴蜀定理，存在当且仅当。求解模意义下逆元只需求解线性同余方程即可。
cpp
```
int inv(int a, int p) {return exgcd(a % p, p, a, *new int), (a % p + p) % p;}
```
1. 通过 exgcd 我们可以证明在当时无解，否则在中有个整数解。这是因为其通解可写为的形式，其中：将方程两侧同时除以，则。
2. 从裴蜀定理的推导过程中，我们证明了这样一个引理：若，则取遍。这是一个很有用的事实。
1.5 例题

I. UVA10104 Euclid Problem

exgcd 的模板题。

II. P5656【模板】二元一次不定方程 (exgcd)

题目要求是正整数，可以先求出的最小正整数值，此时。若则有正整数解，且对应正整数解中最大的，否则没有正整数解。对于和同理。
cpp
```
#include <bits/stdc++.h>
using namespace std;

#define int long long
int T, a, b, c;
void exgcd(int a, int b, int &x, int &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
signed main() {
	cin >> T;
	while(T--) {
		scanf("%lld %lld %lld", &a, &b, &c);
		int d = __gcd(a, b), x, y, xx, xy, yx, yy;
		if(c % d) {puts("-1"); continue;}
		exgcd(a, b, x, y);
		x *= c / d, y *= c / d;
		xx = x % (b / d);
		if(xx <= 0) xx += b / d;
		xy = (c - a * xx) / b;
		yy = y % (a / d);
		if(yy <= 0) yy += a / d;
		yx = (c - b * yy) / a;
		if(xy <= 0) cout << xx << " " << yy << "\n";
		else cout << (yx - xx) / (b / d) + 1 << " " << xx << " " << yy << " " << yx << " " << xy << "\n";
	}
	return 0;
}
```
*III. UVA12775 Gift Dilemma

题意简述：给出，求非负整数解的个数。

题目条件即。对于这种三元不定方程，考虑枚举前的系数，再求的非负整数解的个数。

记，则时间复杂度为。

IV. 某模拟赛你还没有 AK 吗

分别从和中随机选择，求执行任意正整数次以及后使得的初始值的个数。，。时限 1s。

转化题意，令，则相当于求有多少对满足。

注意到斐波那契数列的增长相当快，当光是就已经显然不符题意，故考虑直接枚举。

问题转化为求关于的二元一次方程有多少解满足，（斐波那契数列相邻两项，故不需求）容易 exgcd 求解。但无法通过。

不难发现只有本质不同的对，故预先存储下来即可将复杂度优化至。更进一步地，我们有（可以归纳证明以及上述结论），故直接令即一个合法解，甚至不需要使用 exgcd。

*V. P3421 [POI2005]SKO-Knights

巧妙线性代数题。题目要求我们找到两个向量，使得它们的 整系数 线性组合得到的线性空间（简称整系数线性空间）等价于给出的所有向量的整系数线性空间。定义表示向量集合的整系数线性空间，即

如果我们能将三个向量合并成与之等价的两个向量，就能够解决本题。根据基础的线性代数知识，不改变矩阵行空间的初等行变换有三种：
- 兑换：对应本题即可以任意交换。
- 倍乘变换：对应本题即向量可以乘以任意非整数。
- 倍加变换：对应本题即向量可以加上任意整数倍其它向量。
当然，上述性质仅在 实系数 线性组合的前提下成立。当要求系数为整数时，
- 兑换显然不改变矩阵行空间。
- 倍乘变换 可能改变 矩阵行空间，因为 整数乘法不可逆。如，前者是任意整点，后者是任意纵坐标是偶数的整点。
- 倍加变换 不改变 矩阵行空间：对于任意，它本质上仍是的整系数线性组合。对于任意，我们也总可以将其表示为和的整系数线性组合。
很好！如果整系数倍加变换不改变整系数意义下的矩阵行空间，就可以使用 辗转相减法。具体地，考虑两个向量，我们能够在 不改变其整系数线性空间 的前提下，将的某一维变为。只需对在这一维进行辗转相减法即可。

考虑三个向量，我们对在这一维进行辗转相减，再对在这一维进行辗转相减。此时均为，意味着共线。因此，对在这一维进行辗转相减，就可以使，而变成了 零向量，对没有任何贡献，可以 直接舍去，即此时。

综上，我们在的时间内解决了问题，其中是值域。

注意点：题目限制了坐标绝对值不超过，因此辗转相减法得到最终的时，和是原坐标的，显然满足坐标限制。但不一定，因此要对取模，也相当于做了一步辗转相减（此时所以不需要改变）。故最终得到的坐标绝对值不超过，比题目限制优一个数量级。

从上述过程中，我们也可以发现一个有趣的性质：整系数 意义下，两个向量可以在不改变其张成的前提下，使其中一个向量的 某一维变成 ，而另一个向量的对应维变成原来两个向量在这一维上的。这也是解决本题的关键性质。

因此，推广到任意维度，给定个维向量，我们可以求出这组向量在整系数意义下的基。诶，等等？这不就是 线性基 么！

让我们更加深入地钻研一下题解区的做法。

实际上两者的核心思想是等价的，均为刚才提到的性质：将两个向量的其中一个的某一维变成，另一个的对应维变成。不同点在于本文的线性代数做法是从 倍加变换 和 辗转相除法 开始，推得这一核心思想，即我们运用正确性有保证的方法，最终得到的结果是这样一个性质。而题解区做法是首先令这一条件成立，再根据得到的线性方程组，使用 exgcd 和一些数学推导求解。这也体现了 exgcd 与辗转相除的本质联系。

不妨设对于向量，我们要将变为。此时已经确定，即。因此，对于方程，容易用扩展欧几里得算法求得一组解，则。这是因为。对于向量，有，因此有线性方程组

注意该方程组的与之前 exgcd 求得的不同。同时我们需使 绝对值最小，否则可能出现，但的情况，即对于中横坐标为的所有点，不是与相邻的那一个，这样与相邻的点无法表示。

根据第一个方程，得到的关系式。带入第二个方程，得到，即

我们的目标很明确：找到 绝对值 最小的合法的。把写成的形式（因为分母是），那么，因此满足

注意到若满足前两条限制，则第三条限制自动满足，故忽略。为使的绝对值最小，的绝对值应尽量大。到这一步，大家应该都能看出应取。因此，。

综上，我们将原向量写成了另两个向量，其中，用 exgcd 求解，，。对做一遍类似的操作，再合并（即类似线性代数解法，令，然后丢弃）即可。时间复杂度也是线性对数。

另一种求解的思路（来源于 TheLostWeak 的博客）：可以整系数线性组合出，否则显然不满足条件，因为。

根据上述性质，考虑。由于，所以为了使横坐标等于，需要为乘以即的系数，得到。由于我们可以通过向量得到，因此。同理，。故

易证若小于上述，将导致存在，。若大于上述，无法整系数线性组合出中的至少一个。

联立后两种方法描述的式子，稍作化简后得到等式。这也许说明了某些性质，但笔者已经不想研究了 QAQ，感兴趣的读者可自行钻研。

*VI. P3518 [POI2011]SEJ-Strongbox

若在群里，则所有且是的倍数的数也在群里。这是因为取到了所有这样的数。证明：设，且不在群里，这意味着即无解，根据裴蜀定理，它等价于即，矛盾。证毕。

因此，考虑枚举这个，若合法则答案即，即我们需要找到最小的合法的。

如何判断合法：不妨设，首先得是密码与的即的因数，其次任何不能是的倍数。

考虑后者限制：给所有打上标记，从大到小枚举的每个因数，若被打上标记，则也应被打上标记（其中表示能整除的的质因子），表示若是某个的因数，则显然也是。

剩下来没有被打上标记的所有的因数，若能被整除则合法。找到最小的这样的，则答案为。

打标记的过程用哈希表实现，时间复杂度。表示的质因数个数。

*VII. P7325 [WC2021] 斐波那契

首先我们需要这样的事实：普通斐波那契数列在模意义下纯循环，且循环节长度为。证明过于复杂，略去，读者可当作结论背诵。

，的第项等于，独立前的系数可得该结果。

首先特判的情况。

令，则问题等价于

自然，我们希望将移到方程左侧，移到方程右侧，这样可以直接预处理所有的值。但是并不是质数，因此需要化简。
- 化简使用的核心思路是，同余方程等价于，其中均为代数式，。直观理解很显然，感性说明就是在该同余方程中完全没有起到任何作用。
令，等式两侧同时除以，得到

欲将等式两侧同时除以，即保证在模意义下有逆元，则需。但并不一定满足。

令。根据既约性，，因此必然有，因为方程右侧是的倍数。因此，

此时可以将除过去了。

欲将等式两侧同时除以，需满足，因为斐波那契数列的性质，而等式右侧必须是的倍数，这意味着这个只能等于。

上述推导过程说明我们需要枚举和，并将作为三元组塞入 map 方便查询。根据一开始的结论，复杂度是的所有因数的因数和，再乘以 map 的，无法承受。此时需要利用使得方程有解时这三个变量必须满足的性质降低复杂度。

注意到且，这说明枚举之后，只能等于。即不需要枚举，它随着的确定而确定。这样复杂度变成即的约数个数和，大约是量级（证明详见 p7325 - ycx's blog），因此总复杂度即。
- 注意，当或等于时，直接忽略，因为和不可能同时为，因此等式两侧有一处非零，一处为零（的情况已经特判掉了），矛盾。
总结一下，我们在整个化简过程中，假设了和两个仅与有关的变量，因此预处理时需要枚举和。但根据方程有解时和所具有的性质，我们得以降低复杂度。这种思想方法（在回答多组询问时，为了解决问题，需要设和询问参数相关的变量，那么在预处理时枚举这些变量的所有情况，即可考虑到给定询问参数的所有情况）是很巧妙的，读者需仔细体会。

代码。

2. 欧拉函数

欧拉函数是一类非常重要的数论函数。

2.1 定义与性质

欧拉函数定义为在中与互质的整数的个数，记作。

性质 1：若为质数，则。

证明：在中所有不是的倍数的数都与互质。因此，或者写成。得证。

性质 2（积性）：是 积性函数。即若，则。

证明：设与互质的数为，那么在内与互质的整数可以表示为。

因为，所以在模意义下互不相同（1.4 节性质 4），即对于每一个，均构成的完全剩余系，即随着从变为，模的余数取遍。

因此，对于每一个，满足的的个数为。因此，与互质的数的个数为，即为积性函数。得证。

性质 3（计算式）：根据算数基本定理，设被唯一分解为，则。

证明：根据性质 1 和性质 2，

得证。这是求解的常用方法。

这个性质也可以通过 容斥原理 证明，而不需要性质 1，2。考虑去掉所有被至少一个的质因子整除的数，再加上至少被两个的质因子整除的数，以此类推，最终可以得到式子，其中是的质因子集合的子集。容易证明其等于。

这样可以反推出性质 2：设，。由于，所以互不相同。因此，即

cpp
```
int phi(int x) {
	int ans = x;
	for(int i = 2; i * i <= x; i++)
		if(x % i == 0) {
			while(x % i == 0) x /= i;
			ans = ans / i * (i - 1);
		}
	return ans / x * max(1, x - 1);
}
```
性质 4：若为质数，则。

证明：根据质数的定义可知，故。

性质 5：若，则。
证明：对比与的公式，因为，所以是相同的，只是左边的变成了。故。
- 直观理解：因为相较于并没有增加更多质因子，所以原来与互质的数仍然与互质，而当中与互质的数的个数显然为，因为一个与互质的数加上后仍然与互质。
性质 6（线性筛欧拉函数）：若为质数且，则

由性质 1，4，5 可得。这一性质是线性筛欧拉函数的关键结论。

性质 7（欧拉反演）：。

证明：令是的整数，，则。根据这一点，使得的的个数即。因为，则

得证。如果读者了解狄利克雷卷积，会发现这是。

性质 8：。证明：若，则，故所有小于且与互质的数能一一配对。一个特例是时，此时，。得证。

性质 9：若，则。根据欧拉定理的计算式易证。

性质 10：使得且的的个数为。

证明：容易证明的充分必要条件为。因为，所以。因此合法的的个数为。得证。

将的限制改为，命题仍成立。因为在模意义下等于，或者理解为。
- 简单地说，首先显然得是的倍数，其次不能和有公因子，否则就会大于。
2.2 欧拉定理

回顾费马小定理的证明过程，我们发现不需要是质数这一条件，当时即互不相同。

同时我们知道，两个模互质的数相乘后仍与互质，因此，我们尝试将费马小定理扩展至更一般的情况。

为了防止出现乘积等于零的情况，我们将研究目标设为的 简化剩余系 而非完全剩余系。

设为的简化剩余系，即所有与互质且模互不相同的数组成的集合。对于任意，若，则根据上述分析，与在模意义下的余数不相等且仍与互质。

因此在模意义下，中每个数乘以后仍与相等。故。显然。等式两边同时除以得到

在计算与模数互质的某个数的幂时，指数可以对模数的欧拉函数取模。可以用来化简公式或减小常数（前提是模数是定值或其欧拉函数容易求得）。

扩展欧拉定理：欧拉定理的扩展版本，如下。

感性证明：当时，不断乘以会让和的不断变大，直到某个特定的之后不再变化，因为此时受到的每个与相同的质因子的次数的限制。令这个为，考虑，显然它们均为的倍数，且除以之后会取遍所有与互质的数，这是因为。根据欧拉定理，有循环节，因此即也有循环节。故从开始，有循环节。

严谨证明 摘自 OI wiki，如下。

对于的次幂模构成的无穷序列，必然存在循环节的开始位置和循环节长度，使得从开始以为循环节长度循环，即对于任意满足。欲证扩展欧拉定理，可证且。

当是质数时，令为去掉所有质因子后的结果，。此时，显然（是的倍数）。因为，故，故。因为，得证。

当是质数的次幂时，令，。由上一条，。因此，即。考虑令，由于，且，所以，即。因为，所以由上一条，，得证。

当时，因为且，所以。如法炮制，令，容易证明且，得证。

当为多个质数的乘积时，可以利用上一条类似证明。扩展欧拉定理得证。

扩展欧拉定理的应用见例 IV, V.

2.3 线性筛欧拉函数

根据欧拉函数的性质 6，我们可以线性筛出所有数的欧拉函数。关于线性筛，见各类反演与狄利克雷卷积第六章线性筛部分。

初始化。对于每个质数，。枚举所有数并遍历所有筛到的素数。若，则。否则，同时根据线性筛的算法，此时应退出遍历。
cpp
```
int cnt, pr[N], phi[N], vis[N];
void sieve() {
	phi[1] = 1;
	for(int i = 2; i < N; i++) {
		if(!vis[i]) pr[++cnt] = i, phi[i] = i - 1;
		for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
			vis[i * pr[j]] = 1, phi[i * pr[j]] = (pr[j] - 1) * phi[i];
			if(i % pr[j] == 0) {phi[i * pr[j]] = pr[j] * phi[i]; break;}
		}
	}
}
```
2.4 例题

I. SP4141 ETF - Euler Totient Function

欧拉函数模板题。

II. UVA10179 Irreducable Basic Fractions

根据既约分数的定义且可知答案即。

III. UVA11327 Enumerating Rational Numbers

本题是上题的变形。样例告诉我们分母不大于。因此预处理出每个数的欧拉函数。从小到大枚举分母，求出分母后再根据剩余个数从小到大枚举分子。

*IV. P4139 上帝与集合的正确用法

题意简述：求，。

初看这个无限幂塔读者可能摸不着头脑，因为直觉告诉我们这个值不存在，就好像是一个不确定的数一样。但反直觉的是当足够大时，与在模意义下相同。见高德纳箭号表示法。

为什么呢？根据扩展欧拉定理，上面的幂塔等于，不断使用扩展欧拉定理得到

因为幂指数无穷叠加，所以不需要担心出现导致扩展欧拉定理失效，可以递归实现。

又因为且，所以的迭代值会以指数方式减小为。此时不用关心继续往上的幂次是多少了，因为任何数模都得，这是终止条件。综上，线性筛出以内所有数的欧拉函数即可做到时间复杂度。每次直接暴力算也可以通过。
cpp
```
int F(int x) {
	if(x <= 2) return 0; int v = phi(x); 
	return ksm(2, F(v) + v, x); // 2 ^ {F(v) + v} % x
}
```
*V. P3747 [六省联考 2017] 相逢是问候

根据上一题的结论，在迭代次数足够多时为定值：迭代次数为使得的迭代次数，为级别。

预处理出每个数迭代次后的结果，即对每个位置预处理幂塔迭代次之后的结果（不是，因为最顶上的模的数是而不是），然后对每个线段树上的叶子结点记录操作次数最小值，如果还有可以操作的区间即则递归下去暴力修改。

此外，判断指数是否大于等于可以在快速幂时实现：乘完先不取模，如果值不小于模数再记录并取模。这部分比较细节，需要多加注意。

时间复杂度是：欧拉函数有种，线段树上个位置每种欧拉函数递归层，每次修改都要快速幂。注意到只有种模数，所以可把快速幂换为光速幂。时间复杂度。代码。

3. 离散对数问题

离散对数问题即在模意义下求解。这等价于求解离散对数方程

其中即。模意义下的可能不存在，也可能存在多个，我们的目标是找到任意一个。

当互质时，我们可以使用大步小步算法求解。当不互质时，可以使用扩展大步小步算法求解。

3.1 大步小步算法

大步小步算法全称 Baby Step, Giant Step，简称 BSGS。普通 BSGS 适用于的情况。

大步小步算法运用了 根号平衡（或称为 meet-in-the-middle）的技巧：设块长为且，则有。直接枚举与所有可能的取值并通过哈希表（pb_ds 的 gp_hash_table <int, int>）判断是否相等，即可求出。注意到（根据欧拉定理，若有解，则必然存在解在范围内），将块长设为即可取到最优复杂度。
cpp
```
int BSGS(int a, int b, int p) {
	int A = 1, B = sqrt(p) + 1; a %= p, b %= p;
	gp_hash_table <int, int> mp;
	for(int i = 1; i <= B; i++) mp[1ll * (A = 1ll * A * a % p) * b % p] = i;
	for(int i = 1, AA = A; i <= B; i++, AA = 1ll * AA * A % p)
		if(mp.find(AA) != mp.end()) return i * B - mp[AA];
	return -1;
} 
```
容易发现 BSGS 求得的是的最小的非负整数解，因为我们从小到大枚举指数。

关于即使得成立的的循环节长度，详见 6.1 阶。

3.2 扩展大步小步算法

对于更加 general 的离散对数方程，如果没有该怎么办呢？

核心思想是从已知到未知：既然有了可以解决的 BSGS，那么我们尝试把凑成互质。如果给等式两边同时除以，则方程变为。若显然无解。

注意到，因此前者在模后者意义下存在逆元。但因为可能不是质数，故需 exgcd 求解逆元。移项，方程变为，等式右边可视作常数。

因为与可能不互质，如，，故重复上述操作直到互质，此时直接使用 BSGS 求解即可。

设提出的的个数为，即时上述操作的次数，则求得的解还应加上。注意在每一次操作开始前特判，此时答案等于。

时间复杂度，分别是 BSGS 以及求次和乘法逆元的复杂度。代码见例题 III.

3.3 例题

I. P3846 [TJOI2007] 可爱的质数 /【模板】BSGS

BSGS 模板题。

II. P2485 [SDOI2011]计算器

操作 1 快速幂，操作 2 exGCD 求逆元，操作 3 BSGS。

III. SP3105 MOD - Power Modulo Inverted

exBSGS 模板题。
cpp
```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

int a, p, b;
void exgcd(int a, int b, int &x, int &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p) {return exgcd(x, p, x, *new int), (x % p + p) % p;}
int BSGS(int a, int b, int p) {
	a %= p, b %= p;
	int A = 1, B = sqrt(p) + 1;
	gp_hash_table <int, int> mp;
	for(int i = 1; i <= B; i++) mp[1ll * (A = 1ll * A * a % p) * b % p] = i;
	for(int i = 1, AA = A; i <= B; i++, AA = 1ll * AA * A % p) if(mp.find(AA) != mp.end()) return i * B - mp[AA];
	return -1;
}
int exBSGS(int a, int b, int p) {
	int d = __gcd(a, p), cnt = 0;
	a %= p, b %= p;
	while(d > 1) {
		if(b == 1) return cnt;
		if(b % d) return -1;
		p /= d, b = 1ll * b / d * inv(a / d, p) % p;
		d = __gcd(p, a %= p), cnt++;
	}
	int ans = BSGS(a, b, p);
	return ~ans ? ans + cnt : -1;
}
int main() {
	cin >> a >> p >> b;
	while(a) {
		int ans = exBSGS(a, b, p);
		if(~ans) cout << ans << "\n";
		else puts("No Solution");
		cin >> a >> p >> b;
	}
	return 0;
}
```
IV. P3306 [SDOI2013] 随机数生成器

我们尝试用《具体数学》给出的方法推公式。不妨令下标左移一位，即题目中给出的数视作。

令，那么，即，同时。不难发现，那么

是裸的 BSGS。注意特判和。时间复杂度。

4. 线性同余方程组

前置知识：扩展欧几里得算法。

求解形如

的 线性同余方程组 是信息学竞赛的常见内容。线性同余方程组涉及方面十分广泛（从多模 NTT 到高次剩余），因为它可以处理模数不是质数的情况，或者合并问题中的循环节。
- Note：excrt 比 crt 更容易理解且适用范围更广泛，因此笔者在合并线性同余方程组时一般使用 excrt。
4.1 中国剩余定理

中国剩余定理全称 Chinese Remainder Theorem，简称 CRT。它用于求解 模数两两互质 的线性同余方程组，即对于任意，均有。

CRT 的大致思想是求出若干数，使得这些数依次满足某一个同余方程组，且在其它模数意义下均为。则这些数的和即为所求。

根据上述初步感知，我们令，并尝试为每个同余方程构造，记为条件一；且对于均有，记为条件二。我们将目光放在单个同余方程上。

首先，为满足条件二，应为即的倍数。令其为。我们发现令等于即可满足条件二。为满足条件一，我们发现和互质（题目条件可推得），因此只需为再乘上其在模意义下的逆元即可。令为，则满足两个条件。注意，需要通过 exgcd 求解，因为可能不是质数。

对每个模数均进行一遍上述流程，则即为所求。时间复杂度线性对数。模板题代码见例题 I.

4.2 扩展中国剩余定理

扩展中国剩余定理简称 excrt。它用于求解 一般形式 的线性同余方程组。它和中国剩余定理在本质上没有任何联系，仅是求解的问题形式相同。
- 笔者认为 excrt 更简单一些。
当模数不互质时，考虑合并两个同余方程和。因为可以表示成，所以，即，exgcd 求解即可（或者可以理解为用 exgcd 求逆元，两种方法本质相同）。合并后的方程即。

根据裴蜀定理，若，则方程组无解。时间复杂度线性对数，模板题代码见例题 II.
- 记得考虑 exgcd 解出来是负数的情况。在得到解之后需要进行取模。
4.3 例题

I. P1495 【模板】中国剩余定理(CRT)/曹冲养猪

中国剩余定理模板题。注意要使用 int128 或慢速乘。
cpp
```
#include <bits/stdc++.h>
using namespace std;

const int N = 10 + 5;
int n, a[N], b[N];
long long M = 1, ans;
void exgcd(int a, int b, int &x, int &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p) {return exgcd(x, p, x, *new int), (x % p + p) % p;}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i], M *= a[i];
	for(int i = 1; i <= n; i++) ans = (ans + (__int128)b[i] * (M / a[i]) * inv(M / a[i] % a[i], a[i])) % M;
	cout << ans << endl;
	return 0;
}
```
II. P4777 【模板】扩展中国剩余定理（EXCRT）

excrt 模板题。
cpp
```
#include <bits/stdc++.h>
using namespace std;

long long n, a, b, c, d;
void exgcd(long long a, long long b, long long &x, long long &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
	cin >> n >> a >> b;
	for(int i = 1; i < n; i++) {
		cin >> c >> d;
		long long e = __gcd(a, c), f = (d - b % c + c) % c, inv;
		c /= e, f /= e;
		exgcd(a / e, c, inv, *new long long), inv = (inv % c + c) % c;
		b += (__int128)f * inv % c * a, a *= c, b %= a;
	}
	cout << b << endl;
	return 0;
}
```
III. P4774 [NOI2018] 屠龙勇士

设第次选用的剑的攻击力为，可以通过 multiset 模拟确定。问题转化为找到最小的使得对于所有都有且。

先求出，若则无解，否则将同时除以，此时有，把除过去就是标准的线性同余方程组。excrt 求解得到。

为满足第二个条件，我们可以先求出表示打败 Boss 至少要多少次攻击。若最终求得的，那么需将加上，其中是最终的同余方程的模数。时间复杂度线性对数。代码。

IV. P4621 [COCI2012-2013#6] BAKTERIJE

细菌的运动情况会在不超过次后形成循环，因此先 BFS 找环，特判前次运动，然后枚举每个细菌进入时的方向，从而唯一确定一个线性方程组，excrt 即可。

时间复杂度，其中是值域。由于每次添加的模数很小，只有级别，可直接循环枚举。

V. P2480 [SDOI2010]古代猪文

求。指数对取模，分解质因数后发现是 square-free number，直接 lucas + crt 即可。时间复杂度。

lucas 见第八章。

5. 数论分块

数论分块又称整除分块，因其解决的问题与整除密切相关而得名。具体地，数论分块用于求解形如

的和式。前提是的前缀和容易快速计算。

读者需要有这样的感性认知：使得除以下取整后等于的正整数的范围为，即。

5.1 算法介绍

部分摘自 OI wiki。

感性认知：当较大时，的取值很多，但被限制在较小的范围内，因此很多均相同。
- 数论分块的时间复杂度基于以下引理（记作引理 5.1）：对于任意以及，不同的至多个。证明：当时，显然只有个。当时，，因此也只有个。证毕。
- 数论分块的正确性基于以下（记作引理 5.2）引理：。即先除以一个数，下取整后再除以一个数再下取整，等于除以这两个数的乘积后下取整。证明：令，则。因为，而均为整数，所以可忽略。证毕。
数论分块的结论如下：对于，使得的最大的等于。显然存在，因为是的一个合法取值。

感性证明：令，。因是整数，故。读者也可根据本章开头部分的感性认知来理解。

严谨证明：令，则。根据引理，，所以等于的最大值即。若还可以更大，即，则，根据引理，即，即。这和矛盾。证毕。

通过上述分析，我们得到了数论分块算法的大致轮廓，如下所述。

设为的前缀和。从开始，每次令，然后将答案加上。最后令，若大于则退出。

根据引理 5.1，每个不同的仅会被遍历一次，故时间复杂度。
- 注意，当的上界不等于时，不妨设其为，则应当与取较小值（时会出现该情况），且当时需要特判，直接令等于（时会出现该情况）。
5.2 扩展

5.2.1 向上取整

尝试将向下取整变为向上取整。

对于左边界，我们求出使得的最大的。不妨设，则

第二步转换是因为均为正整数。上述推导类似向下取整时的感性证明部分。

因此，我们只需令即可。

注意特判的情况，此时的上界为无穷大，需要与实际上界取较小值。

5.2.2 高维数论分块

当和式中出现若干下取整，形如

时，只需稍作修改，令即可。不要忘记对取。

时间复杂度为。将令的位置视作断点，则总共的断点数量为每个下取整式的端点数量相加（而非相乘），而我们只会在每个断点处遍历一次，故有该时间复杂度。

5.3 例题

I. 某模拟赛你还没有卸载吗

给定，求有多少使得。，其他所有数。时限 1s。

笔者尝试用数学方法推导答案，无果。故考虑数论分块固定，解出，从而反推出合法的的范围：。时间复杂度。

另一种方法是直接二维数论分块。细节更少，且时间复杂度不变。

启示：当用数学手段推导公式无果时可以考虑固定一些变量。
cpp
```
#include <bits/stdc++.h>
using namespace std;
int T, a1, b1, a2, b2, n;
int main() {
	cin >> T;
	while(T--) {
		int ans = 0;
		cin >> a1 >> b1 >> a2 >> b2 >> n;
		for(int l = 1, r = 1; l <= n; l = r + 1) {
			r = min(n, min(a1 / l ? a1 / (a1 / l) : n, a2 / l ? a2 / (a2 / l) : n));
			if(b1 + a1 / l == b2 + a2 / l) ans += r - l + 1;
		}
		cout << ans << endl;
	}
	return 0;
}
```
II. *CF1603C. Extreme Extension

数论分块优化 DP。

一个数如何分裂由后面分裂出来的数的最小值决定，而显然我们一定是贪心使分出来的数尽量均匀，例如若要裂成若干个比小的数那么就比更优。

这启发我们从后往前考虑：对于每个数和数值，求出有多少个以开头的子串使得分裂出的最小值为，即求出的个数使得根据上述贪心所分裂出来的数的最小值为（显然这个也必须由分裂零次或若干次得到），记为，那么答案加上：因为至少要分裂次才能让，而以开头的每一个子段的左端点还可以被向左扩展次。即若子段在处至少分裂次，则对于任何子序列，分裂的次数都是，因为的分裂不受前面的数的影响。这样的共有个，故需乘上（也就是说，我们在每个位置处统计该位置在所有子段中总分裂次数之和）。

看上去有个合法状态，但有些是永远分裂不到的，例如若则无用，因为如果要使得分裂出来的数，则根据贪心思想我们会分成而不是。类似的，也无用。

实际上只有所有有用，这一点不难证明（注意，给定分裂得到的值计算 分裂次数 是上取整，但给定分裂次数计算 分裂得到的值 是下取整）。而根据数论分块的结论，有用的只有个。

因此，我们可以直接枚举表示用整除 上取整 后结果相同的一段区间，这个可以类似数论分块实现，详见基础数论学习笔记 Part 5.2.1（数论分块是下取整后相同，而本题是上取整后相同）。则可以由得到，其中。

上述转移式的来源：给定值，要求分裂出来的数均，因为我们需要 使分裂次数最小，因此分裂次数是固定的。因此，使分裂次数相同的值即使整除后上取整相同的一段值域区间。同时，我们分裂得到的数的较小值即，因为分裂了次。

用不定长数组 vector 来存储每一位的答案，时间复杂度，空间复杂度。代码。

III. P2260 [清华集训2012]模积和

求是经典问题：拆成后数论分块，时间复杂度。

原式可以写作

全部可以使用数论分块解决。可能需要的公式：。时间复杂度。

6. 阶与原根

原根，数论的王！

模的简化剩余系在模乘法意义下封闭且构成群。容易证明其满足封闭性和结合律，存在逆元和单位元。将群相关定义应用在其上，得到阶和原根（循环群的生成元）的概念。

6.1 阶

阶的定义如下：使得的最小的 正整数 被称为模的阶，记作。

容易发现，是存在的 充要条件。必要性：若与不互质，显然与不互质，因此模不可能得。充分性：若，根据欧拉定理，即一解，因此阶存在。
- 阶就是将一个数自乘若干次后模，第一次得到的自乘次数。之所以是得到，因为的性质很好。例如它和所有数互质，且的任何次幂均为，且是在模任何正整数意义下的乘法逆元，因此我们可以在同余方程的任意位置除以已经被证明等于的部分，而不需要担心不存在逆元。
接下来给出一些关于阶的性质。以下讨论均基于。
- 若，则。因此所有使得的必然是即的倍数。
性质 1：当且仅当。若非，则令，，与阶的最小性矛盾。

性质 2：。OI wiki 的证明较为复杂，笔者给出一个感性理解。
- 对于第一部分，注意到，因此根据性质 1，为最小的使得，因此（我们知道，若给定，则使的最小的为，这一点可以对的每个质因子单独分析得到）。
- 对于第二部分，因为能够整除的最小的的倍数为（根据最小公倍数的定义易得），所以使得的最小的即，故。
- 上述两部分也可以根据互相推导。
回收前文（3.1 BSGS）：当时，使得的 若存在，则有循环节。证明显然。因此，为求出的通解，我们可以求出的最小解和次小解，则，因为。

下面给出求解的若干方法，其中。

法一：直接使用 BSGS 求的最小正整数解。时间复杂度。

法二：根据阶的性质 1，对于，必然有。因此考虑首先令，然后对于的每个质因子，用不断试除直到无法整除或。时间复杂度，因为需要分解质因数和求解欧拉函数，用 Pollard-rho 可以优化至。若不大，则可线性筛预处理每个数的最小质因子，单次查询即可。

6.2 原根

原根的定义如下：对于，且，若，则称为模的原根。

注意，并不是所有数均有原根。存在原根的模缩系同构于循环群，因为原根这一概念等价于循环群的生成元。

我们需要原根的原因是它可以生成模的缩系，即它的若干次幂在模意义下取遍了所有与互质的数。这使得我们在考虑解与模数互质且模数存在原根的同余方程时可以用原根的若干次幂代替未知数。这一点在求解高次剩余时非常有用。
- 我们将在众多数论毒瘤题中体会到原根威力之强大：它可以将指数上的问题转化为更简单的一般问题。
根据原根的定义，为判定是否是的原根，只需检查的所有的 真因数 次幂模是否均不等于。这等价于检查除以其质因子是否是的阶的倍数，因为除以其某一质因子所得的所有数覆盖了的所有真因数。因此，我们有

原根判定定理：对于，，是的原根的 充要条件 是对于任意的质因子，均有。

证明：必要性显然。

充分性：因为的所有因子取遍了除了其本身的所有因子，所以若存在使得（容易证明），则必然存在的质因子使得，这说明存在，与假设矛盾。证毕。

除了判断一个数是否是原根，我们也需要判断一个数是否有原根。

原根存在定理：一个数存在原根的 充要条件 是，其中是 奇质数。

证明过于复杂，略去。读者可以当成重要结论记住。

以下是原根与阶相结合的一些知识。

若存在原根，则使得的的个数为。

根据阶的性质 1，第一部分显然。

考虑证明第二部分：设为的一个原根。因为对于任意均可表示为，所以问题即求出使得的的个数。根据阶的性质 2，，因此，即。根据欧拉函数的性质 10，满足该式的个数即，即。
- 形象地说，将看成一个长度为的环。我们尝试在环上每次走步形成一个子环，则的阶即形成的环长。我们知道，如果在一个长为的环上每次走步，则能够走到的位置模相同，且模相同的位置均能被遍历到（这是 OI 中的经典结论，见 0.7），即环长为。因此，为使，即，即环长和步长的等于形成的子环个数，也等于环长除以子环长。根据欧拉函数的性质 10，合法的的个数即。
上述结论从侧面反映了欧拉函数的性质 7：。，即模的阶等于的数的个数之和（也即在模意义下存在阶的数的个数）等于与互质的数的个数，而与互质是在模意义下存在阶的充要条件。

通过上述推导我们得到推论（原根个数定理）：若正整数存在原根，则其原根的个数为。

求出一个数的所有原根：考虑求出一个数的任意一个原根，根据上述结论，也是的原根。在 1959 年，中国数学家王元证明了最小原根的级别为。结合原根存在定理和原根判定定理，我们得以在预处理每个数的最小质因子后单次求出的最小原根，从而求出的所有原根。
- 笔者在上网查找资料时发现中国科学院院士王元于 2021 年 5 月 14 日去世，为此笔者深感痛心。可能这位前辈也没有想到，在六十多年后的今天，他的研究成果已经成为信息学竞赛中数论领域的重要一环。笔者在此对他表示崇高的敬意。
关于原根，还有一个有趣且重要的性质：

若存在原根，设，则的简化剩余系与次单位根同构。

这是因为对于任何一个，其均可以写成的形式。而任何一个次单位根也可以写成的形式。同时，，且。因此，我们可以将单位圆应用在的简化剩余系上，为原根提供了一个形象的表示方法，如下图。

图中，单位根的次幂将单位圆若干等分。次单位根恰好对应着，圆环上运算（两个数相乘）的循环往复（体现为逆时针旋转）体现了模这一操作。

这也是为什么对于特定模数，我们可以使用原根代替次单位根进行快速傅里叶变换：，所以当需要使用次单位根时，若不超过当中质因子的个数且存在原根，即可用原根代替次单位根。也就是快速数论变换 NTT。

6.3 相关应用

总结一下，我们提出阶的定义是为了引出原根（至少在笔者所接触过的所有题目中，没有遇到直接与阶相关的问题），而原根的用处在于生成模的简化剩余系。不要小看这个性质！它在是质数或质数的幂时非常好用，可以生成除了以外的任何数，几乎是神一样的存在！

我们介绍了阶的相关性质及其求法，以及原根的判定定理，存在定理与个数定理。其中，原根存在定理和最小原根级别的证明较为复杂，故略去，学有余力的读者可自行查阅资料。
- 在特定模数下，原根用于替换复数单位根进行快速傅里叶变换，如常见 NTT 模数，等等。
- 求解高次剩余时，一步重要的转化是 将未知数用原根的若干次幂代替。
6.4 例题

*I. P5605 小 A 与两位神仙

前置知识：Pollard-rho & Miller-Rabin。

注意到模数是奇质数的幂，存在原根。

尝试将和表示成和的形式，则根据欧拉定理，等价于方程。

根据裴蜀定理，后者存在解的充要条件是，这等价于。

根据阶的性质，我们发现（其实这很好理解，在长为的环上每一步走长度，则需要步才能回到原来的位置），因此该条件又等价于。

直接求阶即可，在最开始需要使用 Pollard-rho 分解，时间复杂度。

通过本题，我们得到这样的结论：对于奇质数的幂和，有解当且仅当。
- 根据阶的性质，对于，必然有。因此考虑首先令，然后对于的每个质因子，用不断试除直到无法整除或。
*II. P6730 [WC2020] 猜数游戏

和上面一题差不多的思路。

分成与互质和与不互质两种情况考虑。并且将每个数的贡献拆开来考虑，即求出有多少种情况使得对答案有贡献。

当且仅当中不存在一个数能生成时，对答案有贡献。因此对每个 ,答案加上，其中是能生成的数的个数。

当与不互质时，因为是奇质数的幂，所以在不超过次后的幂变为，因此直接考虑每个数能生成哪些数即可得到每个数能被多少个数生成。使用哈希表存储，该部分时间复杂度。

当与互质时，直接使用上一题的结论，对每个数求阶后做高维后缀和即可。注意若两个数能互相生成，即阶相等，则需要钦定一个顺序，使得前面的数钦定生成后面的数。

7. 高次剩余问题
- Warning：本章难度较大。
若在模意义下能表示为某个数的次方，则称为模意义下的次剩余。

次剩余问题即求解形如的方程。注意未知量在底数处，而非离散对数问题的指数处。

7.1 拉格朗日定理

我们知道代数学基本定理：任何次多项式在复数域有且只有个可重根。那么，在模意义下是否仍然满足多项式的不同的根的个数不超过多项式次数呢？

拉格朗日定理告诉我们如下事实：对于模质数意义下的整系数多项式，其中，则在模意义下至多有个不同解。

证明：考虑数学归纳法。当时成立，因为无解（注意）。

当时，不妨设方程有个不同解。因为，所以必然可以被因式分解为，其中是一个不超过次的多项式。

因为且，故均为的根，与归纳假设矛盾。命题得证。

7.2 二次剩余

7.2.1 定义与符号

根据定义，若存在使得，则称为模的 二次剩余，反之则称为模的 二次非剩余。注意，这两个定义均基于不是的倍数的基础上。也就是说，若是的倍数，则既不是模的二次剩余，也不是模的二次非剩余。

勒让德符号：记作。当是模的二次剩余时，该值为；当是模的二次非剩余时，该值为；当是的倍数时，该值为。
- 勒让德符号在二次互反律的表示中很有用，但是我们不讲二次互反律。
- 直观认知：能被表示成的数是二次剩余，反之则是二次非剩余。设，，则。要使，则。因为是偶数，所以当为奇数时，无解，反之则有两解（详见 1.4 节第三条），每一个的解对应一个。
7.2.2 二次剩余的数量

以下讨论均基于为奇质数。

根据拉格朗日定理，对于二次剩余，使得成立的不同的恰有两个。不妨设为其中一解，显然也为一解，且因是奇质数所以。这说明若为模的二次剩余，则存在两个不同且互为相反数的使成立的。

如果不用拉格朗日定理，我们也可以证明这一结论（思路来自 Kewth，详见参考资料）：设和是任意两个不同的使方程成立的解，则，即。所以。这说明和互为相反数。我们知道，一个数的相反数只有一个，因此至多且必然有两解（因为是二次剩余）。
- 这和实数意义下的平方根几乎完全一样：正数（二次剩余）的平方根有两个且互为相反数，负数（二次非剩余）没有平方根。
因为当中任意一对相反数平方后均给出相同且独一无二的二次剩余，故模奇质数意义下二次剩余的数量和二次非剩余的数量均为。
- 感性认知：所有原根的偶数次幂和所有原根的奇数次幂将分成了两类，偶数类对应二次剩余，奇数类对应二次非剩余。
7.2.3 欧拉判别准则
- 的偶数倍一定是的倍数，而的奇数倍一定不是。，而。
利用欧拉判别准则，我们可以判断一个数是否是 奇素数 的二次剩余。它给出如下定理：

也就是说，当是二次剩余时，。当是二次非剩余时，。

证明（来自 Kewth）：时定理显然成立，考虑。根据费马小定理，。所以只能等于或。因此欲证欧拉判别准则，只需证当且仅当是二次剩余。

充分性：当是二次剩余时，令。显然，因此。

必要性：因为是奇素数，故存在原根。不妨设。根据原根的定义，，故。因为，所以为偶数。因此，即为二次剩余。得证。
- 另一种理解方法：当为奇数时，。根据 6.2 节中提到的等价类与单位根的同构性，上述事实恰对应着次单位根当为偶数时，当为奇数时。
  
  简单地说，是否是二次剩余 等价于 是否等于 等价于 能否被表示成的一个原根的偶数次幂。读者应当仔细体会其中的等价关系。
欧拉判别准则同时也告诉我们勒让德符号关于是完全积性函数，即对于任意，均有。

接下来介绍一个求解二次剩余的常用算法。

7.2.4 Cipolla 算法

Cipolla 可以在时间内求解模 奇质数 意义下的二次剩余，即给定，求出使得的所有（显然有根号时间复杂度求解二次剩余的算法：BSGS）。

根据 7.2.2 节的分析，我们只需求出任意一个，然后取相反数即可。

学习 Cipolla 算法，我们首先需要了解 模意义下扩域 的技巧。读者可以理解为从 “整数” 扩张到了 “整系数复数”。

设为一个二次非剩余，。这样的在模意义下的整数域中不存在，但是我们可以人为规定它存在（类似规定虚数单位存在）。因此我们得到了形如的数。笔者习惯将其称为模意义下以为虚数单位的复数。

即定义数域。容易证明该数域封闭（类比复数域封闭），如乘法运算法则即，且满足我们常见代数结构的几乎所有代数性质，如乘法结合律，乘法分配律等。

这个技巧常见于 模意义下二次非剩余强制开方。例如，在模意义下没有二次剩余，故在计算斐波那契数列时，需要将一个数表示为的形式。
- Warning：前方有魔法。
考虑找到一个正整数使得为二次非剩余，令，即。我们断言为的二次剩余。

证明 Cipolla 算法的正确性需要两个引理。
1. 。由欧拉判别准则，。
2. 。由二项式定理，，因为当时，的分子含有质因子而分母不含，故为的倍数。因此我们只需保留和的项，即（有读者可能会因为是模意义下复数而产生疑问，设，则）。
证毕。

接下来是一些需要处理的细节。
1. 可以证明当随机时，的二次剩余性均匀随机（但是笔者查阅的所有资料均没有给出完整证明，故略去）。因此，我们期望随机两次就可以找到这样的。
2. 为证明的虚部为，只需证明不存在，其中。假设存在，对比等式两侧虚部，必然有，因此。带入，得。因为和均为二次剩余，所以必然为二次剩余（勒让德符号的完全积性），矛盾。证毕。
综上，Cipolla 算法的时间复杂度为。代码见例题部分 I.

7.2.5 任意模数二次非剩余

什么？怎么会有出题人毒瘤到考这种玩意？

7.2.6 总结

二次剩余相关知识繁多，抓住 原根可近似看做单位根 这一关键线索有助于更好地理解奇素数的二次剩余个数为这一事实与欧拉判别准则。

从另一种角度：当中的奇偶性出发，结合 exgcd 的推论（当不互质时方程的解的情况，详见 1.4 节）也可以推得这些定理。

关于欧拉判别准则，笔者的理解是，对于任意奇素数均有。给指数除以相当于为左式开根。因此，当中的所有数会因为自身性质的不同而分化成两类，一类是二次剩余，满足，另一类是二次非剩余，满足。这种分化，用单位根的知识来解释，即对于次单位根，当为偶数时，反之则为。而原根和单位根的联系

恰好解释了，的奇偶性对是否是二次剩余的影响。

因此，笔者认为理解二次剩余的核心在于体会到 原根和单位根的等价性，以及 原根指数的奇偶性起到的关键影响。这对于理解更高次剩余也有极大帮助。是时候再贴出这张图了。

Cipolla 算法的巧妙构造令人惊叹，可惜的是，

“如果读者或听众不能够理解在人类力所能及的范围怎样可能找到这样一个论证，如果他不能从推导过程中得出任何关于他自己怎样能找到这样一个论证的建议，那么这个推导就可能是难以接受的，而且没有指导意义。”

所以读者只需记住这样的构造：找到使得是二次非剩余，令，则即为所求。需要在模意义下扩域。

扩展：注意到当指数为时，将分成两类。那么，当时，是否有的取值将分成类？实际上是有的，读者可结合次单位根的性质和模的余数尝试推导结论。

7.3 高次剩余

咕咕咕。

7.4 例题

I. P5491 【模板】二次剩余
cpp
```
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int T, n, p, b, w;
struct comp {
	int a, b;
	comp operator + (comp c) {return {(a + c.a) % p, (b + c.b) % p};}
	comp operator * (comp c) {return {(1ll * a * c.a + 1ll * b * c.b % p * w) % p, (1ll * a * c.b + 1ll * b * c.a) % p};}
};
int ksm(int a, int b) {int s = 1; while(b) {if(b & 1) s = 1ll * s * a % p; a = 1ll * a * a % p, b >>= 1;} return s;}
comp ksm(comp a, int b) {comp s = {1, 0}; while(b) {if(b & 1) s = s * a; a = a * a, b >>= 1;} return s;}
void solve() {
	cin >> n >> p;
	if(!n) return puts("0"), void();
	if(ksm(n, p - 1 >> 1) == p - 1) return puts("Hola!"), void();
	do b = rnd() % p; while(ksm(w = (1ll * b * b - n + p) % p, p - 1 >> 1) != p - 1);
	int x = ksm((comp){b, 1}, p + 1 >> 1).a;
	cout << min(x, p - x) << " " << max(x, p - x) << "\n";
}
int main(
	cin >> T;
	while(T--) solve();
	return 0;
}
```
*II. P6610 [Code+#7]同余方程

究极神仙题。

根据不难想到使用 CRT 将问题拆分为模奇质数。每个奇质数的解的个数的积即为所求，因为从每个奇质数的解中任选一个，根据中国剩余定理，所有奇质数对应的解组合起来唯一确定一个解。

拆成奇质数是为了使二次剩余相关定理适用。接下来均视为奇质数。

问题转化为求解能被拆分成多少组的和，使得均为二次剩余或。其中，每个二次剩余的贡献系数是（一个二次剩余可被表示两个数的平方），的贡献是，每组的贡献即和分别的贡献系数之积。

我们需要一个数学公式而非判断式来描述答案，因为判断式是不可化简的。

二次剩余对应，对应，二次非剩余对应，这使得我们想到勒让德符号：注意到等价于使得的的个数，因此答案为

以内的二次剩余和二次非剩余个数相等，故。再根据和勒让德符号的完全积性，上式简化为

接下来是一步巧妙转化。考虑到为除以并不影响它的二次剩余性，因此答案即

显然，对于且，取遍，即取遍。故当时，答案又可写为

根据欧拉判别准则公式上式即。

对于，答案即。

公式已经足够简洁，可以计算。时间复杂度。
cpp
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
int T, p, x, cnt, ans = 1, pr[N], mnpr[N];
bool vis[N];
int calc(int x, int p) {return !x ? p % 4 == 1 ? 2 * p - 1 : 1 : p - (p % 4 == 1 ? 1 : -1);}
int main() {
	for(int i = 2; i < N; i++) {
		if(!vis[i]) mnpr[i] = pr[++cnt] = i;
		for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
			vis[i * pr[j]] = 1, mnpr[i * pr[j]] = pr[j];
			if(i % pr[j] == 0) break;
		}
	}
	cin >> T;
	while(T--) {
		cin >> p >> x, ans = 1;
		while(p != 1) ans *= calc(x % mnpr[p], mnpr[p]), p /= mnpr[p];
		cout << ans << "\n";
	}
	return 0;
}
```
8. 卢卡斯定理

前置知识：组合数，二项式定理。

卢卡斯定理是连接组合数学和数论的重要桥梁。
- Note：相比 Lucas，exLucas 的推导过程更加自然。
8.1 定理介绍

根据 0.6 节的结论，当是质数时，当且仅当减去在进制下需要借位，这等价于在进制下的每一位均不小于。

我们知道，当时，定义为。这启发我们思考，如果将表示为进制数和（不足的位均补，即），那么是否有？

首先给出引理：当是质数时，

是不是感觉非常眼熟？没错，在证明 Cipolla 算法的正确性时我们也使用了该引理。

证明：使用二项式定理将上式拆开，当时是的倍数。证毕。

推论：。

卢卡斯定理有两种等价的表示方法，一是

二是

其中分别是在进制下的表示，即，，且为质数。

容易证明两种形式等价，因此我们只需证明第一种形式。

证明：设，即设，，则

上式前的系数即。

因为展开后的次数均为的倍数，展开后的次数小于，因此项只能由展开后的项与展开后的项相乘得到。根据二项式定理，命题得证。

根据形式 1, 递归实现 Lucas 即可。预处理阶乘及其逆元求组合数，单次 Lucas 的时间复杂度为。代码见例题部分 I.

卢卡斯定理告诉我们，当计算一个大组合数对取模后的值时，可以将在进制下的每一位分开考虑，再将所得结果相乘。

特别地，若在进制下至少有一位小于，则，这是因为对于，。这符合我们一开始的猜想。

利用卢卡斯定理，我们可以快速计算组合数的奇偶性。为使在二进制下每一位均不大于，必然有。因此，是奇数当且仅当和的按位与等于，或者和的按位或等于。

8.2 扩展卢卡斯定理

当模数不是质数的时候，我们也有快速计算的方法。

首先，处理模数为合数的情况，一般的思路是首先将分解质因数为，对模每个质数幂的情况单独求解，再 crt 合并。这就是 crt 的强大威力！

考虑计算。自然是将组合数拆成的形式。因为含有质因子，所以我们无法直接求解逆元。既然这么麻烦，那就除掉好了。

考虑将组合数的分子和分母的所有质因子全部除掉，即变形为

看起来很吓人，但实际上我们只是做了一个简单变形。根据 0.5 节的结论，容易求得（为了求出后面那个的幂次）。

此时分子和分母均不含因子，那么分别算出分子和分母，再对分母求逆元即可。问题转化为求。

设，，。既然除掉了所有质因子，自然想到将所有数分成的倍数和非的倍数讨论。

对于的倍数，有，我们给每个数除掉一个，惊讶地发现问题变成了求。这是一个递归形式的子问题，可以递归求解。当时达到递归边界。

对于非的倍数，它们在模意义下形成循环节

因此我们只需计算（关于记号，详见 0.4 威尔逊定理推论部分）。预处理以内所有与互质的数的积的前缀和，该部分可以计算。
- Note：根据威尔逊定理的推论（详见 0.4 节），等于或。因此第一项不需要快速幂，可以直接根据快速计算。
综合上述讨论，我们得到

当时，直接计算返回预处理结果（因为此时等于），否则使用递归式计算即可。单次时间复杂度。
- Note：递归下去的子问题是除以，而循环节个数是除以，一定要注意区分！笔者因为递归下去的子问题直接除以调了一个小时。
- Note：注意区分和。前者仅将所有质因子去掉，而后者将所有含有质因子的数去掉了。
综上，我们得以在的时间内求出一个大组合数模任意数的值。若模数固定且使用的时间预处理，则可以做到单次。代码见例题 III.

8.3 例题

I. P3807 【模板】卢卡斯定理
cpp
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int T, n, m, p, fc[N], ifc[N];
int ksm(int a, int b) {int s = 1; while(b) {if(b & 1) s = 1ll * s * a % p; a = 1ll * a * a % p, b >>= 1;} return s;}
int binom(int n, int m) {return 1ll * fc[n] * ifc[m] % p * ifc[n - m] % p;}
int lucas(int n, int m) {
	if(n % p < m % p) return 0;
	if(n < p) return binom(n, m);
	return 1ll * lucas(n / p, m / p) * binom(n % p, m % p) % p;
}
void solve() {
	cin >> n >> m >> p;
	for(int i = fc[0] = 1; i < p; i++) fc[i] = 1ll * fc[i - 1] * i % p;
	ifc[p - 1] = ksm(fc[p - 1], p - 2);
	for(int i = p - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % p;
	cout << lucas(n + m, n) << endl;
}
int main() {
	cin >> T;
	while(T--) solve();
	return 0;
}
```
*II. [BZOJ2445]最大团

定义一张个点的图是 “好图” 当且仅当它能被分成若干大小相等的完全图。节点有标号。记个点的好图个数为。求。。

由于模数是质数，根据欧拉定理转化为求。

被分成的完全图大小一定是的约数，考虑枚举并计算完全图大小为时的方案数。

根据组合意义，从个节点中选出个点连成完全图，再从剩下个节点中选出个点连成完全图，以此类推。最后剩下的个节点连成完全图。由于完全图之间无序，而我们枚举完全图的过程有序，因此还需要除以的阶乘。记，则

我们没有简单的办法在优于线性的复杂度内快速计算一个数的阶乘，而且模数也不是质数。

观察，将其分解质因数后得到。这说明模数是 square-free number。考虑分别求上式对这四个质数取模后的结果，最后 crt 合并。

问题转化为计算对质数取模后的结果，其中均较小。

对于给定的，容易算出总共含有多少个质因子，即。因此，先求出含有多少个质因子，若个数则直接返回。否则问题转化为计算一个数的阶乘去掉所有质因子后模的结果，记为。

接下来使用扩展卢卡斯定理的思想。

记以及。我们求出 除去的倍数 后对取模的值，再乘上。因为这些被忽略的数除以后变成了子问题。

因此我们只需求出。将所有对取模，即。根据威尔逊定理，上式即，可以预处理计算。因为最多递归次（每次将除以），因此该部分复杂度。

综上，总时间复杂度。
cpp
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
const int mod = 1e9 - 401;
const int P[4] = {2, 13, 5281, 7283};
int ksm(int a, int b, int p) {
	int s = 1;
	while(b) {
		if(b & 1) s = 1ll * s * a % p;
		a = 1ll * a * a % p, b >>= 1;
	}
	return s;
}
int T, n, m, ans, p, fc[N];
vector <int> factor;
int num(int n) {int s = 0; while(n) s += n /= p; return s;}
int wilson(int n) {
	if(n < p) return fc[n];
	int d = n / p, r = n % p;
	int res = 1ll * wilson(d) * fc[r] % p;
	return d & 1 ? p - res : res;
}
int calc(int d) {
	if(num(n) > num(n / d) + num(d) * (n / d)) return 0;
	return 1ll * wilson(n) * ksm(1ll * wilson(n / d) * ksm(wilson(d), n / d, p) % p, p - 2, p) % p;
}
int query() {
	for(int i = fc[0] = 1; i < p; i++) fc[i] = 1ll * fc[i - 1] * i % p;
	int res = 0;
	for(int d : factor) res = (res + calc(d)) % p;
	return res; 
}
int main() {
	cin >> T;
	while(T--) {
		cin >> n >> m, m %= mod, ans = 0;
		factor.clear(); // add this line =.=
		for(int i = 1; i * i <= n; i++)
			if(n % i == 0) {
				factor.push_back(i);
				if(i * i != n) factor.push_back(n / i);
			}
		int cur = 1;
		for(int i = 0; i < 4; i++) {
			int res = (p = P[i], query());
			int k = 1ll * (res - ans % P[i] + P[i]) * ksm(cur, P[i] - 2, P[i]) % P[i];
			ans += k * cur, cur *= P[i], ans %= cur; // excrt
		}
		cout << ksm(m, ans, mod) << endl;
	}
	return 0;
}
```
III. P4720 【模板】扩展卢卡斯定理/exLucas
cpp
```
#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &x, int &y) {
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p) {return exgcd(x, p, x, *new int), (x % p + p) % p;}
long long n, m;
int p, tp, ans, curp = 1, q, qk, fc[1000005];
long long num(long long n) {long long s = 0; while(n) s += n /= q; return s;}
int calc(long long n) {return n ? 1ll * calc(n / q) * (tp && n / qk & 1 ? qk - 1 : 1) % qk * fc[n % qk] % qk : 1;} // 注意 n / q 和 n / qk!
int solve() {
	tp = (qk & 1) || qk <= 4;
	for(int i = fc[0] = 1; i < qk; i++) fc[i] = 1ll * fc[i - 1] * (i % q ? i : 1) % qk;
	int pw = num(n) - num(m) - num(n - m), res = 1ll * calc(n) * inv(1ll * calc(m) * calc(n - m) % qk, qk) % qk;
	while(pw--) res = 1ll * res * q % qk; // 根据 0.6 的结论, 质因子在组合数中的个数为对数级别
	return res;
}
int main() {
	cin >> n >> m >> p;
	for(int i = 2; i <= p; i++) {
		if(i * i > p) i = p;
		if(p % i == 0) {
			q = i, qk = 1;
			while(p % i == 0) qk *= i, p /= i;
			ans += 1ll * (solve() - ans % qk + qk) * inv(curp, qk) % qk * curp, ans %= (curp *= qk); // excrt 直接合并更方便 
		}
	}
	cout << ans << endl; 
	return 0;
}
```
9. 结语

数论是信息学竞赛的一个广阔分支。尽管近年来重大考试中涉及数论的题目日渐稀少，但熟练掌握数论相关的各种算法及其推导过程，对我们的思维水平有极大锻炼。

因为数论，我们得以求解各种各样的同余方程（，，）；得以利用各种各样的数论函数和反演公式推式子；得以在模数不是质数时将模数转化为质数的幂，为使用原根这一杀手锏提供条件；得以快速计算大组合数取模；我们甚至能够在亚线性时间内计算积性函数前缀和，这无疑是令人惊叹的。希望读者在阅读的过程中能够深刻体会到数论之美。

挖坑待填：
- 任意模数非二次剩余。
- n 次剩余。
- 莫比乌斯反演与狄利克雷卷积的博客的重构。
- 各种各样的筛法，如杜教筛，Min_25 筛。
- 类欧几里得算法。
10. 参考资料
- ycx，数论基础学习笔记。
- OI wiki，数论部分。
- Kewth，二次剩余题解。
CHANGE LOG
0. 前置知识
    0.1 基本定义与记号
    0.2 费马小定理
    0.3 模意义下乘法逆元
    0.4 威尔逊定理
    0.5 素数在阶乘中的幂次
    0.6 素数在组合数中的幂次
    0.7 其它有用的事实
1. 扩展欧几里得算法
    1.1 解的存在性
    1.2 算法介绍
    1.3 解的形式与数值范围
    1.4 应用
    1.5 例题
        I. UVA10104 Euclid Problem
        II. P5656【模板】二元一次不定方程 (exgcd)
        *III. UVA12775 Gift Dilemma
        IV. 某模拟赛你还没有 AK 吗
        *V. P3421 [POI2005]SKO-Knights
        *VI. P3518 [POI2011]SEJ-Strongbox
        *VII. P7325 [WC2021] 斐波那契
2. 欧拉函数
    2.1 定义与性质
    2.2 欧拉定理
    2.3 线性筛欧拉函数
    2.4 例题
        I. SP4141 ETF - Euler Totient Function
        II. UVA10179 Irreducable Basic Fractions
        III. UVA11327 Enumerating Rational Numbers
        *IV. P4139 上帝与集合的正确用法
        *V. P3747 [六省联考 2017] 相逢是问候
3. 离散对数问题
    3.1 大步小步算法
    3.2 扩展大步小步算法
    3.3 例题
        I. P3846 [TJOI2007] 可爱的质数 /【模板】BSGS
        II. P2485 [SDOI2011]计算器
        III. SP3105 MOD - Power Modulo Inverted
        IV. P3306 [SDOI2013] 随机数生成器
4. 线性同余方程组
    4.1 中国剩余定理
    4.2 扩展中国剩余定理
    4.3 例题
        I. P1495 【模板】中国剩余定理(CRT)/曹冲养猪
        II. P4777 【模板】扩展中国剩余定理（EXCRT）
        III. P4774 [NOI2018] 屠龙勇士
        IV. P4621 [COCI2012-2013#6] BAKTERIJE
        V. P2480 [SDOI2010]古代猪文
5. 数论分块
    5.1 算法介绍
    5.2 扩展
        5.2.1 向上取整
        5.2.2 高维数论分块
    5.3 例题
        I. 某模拟赛你还没有卸载吗
        II. *CF1603C. Extreme Extension
        III. P2260 [清华集训2012]模积和
6. 阶与原根
    6.1 阶
    6.2 原根
    6.3 相关应用
    6.4 例题
        *I. P5605 小 A 与两位神仙
        *II. P6730 [WC2020] 猜数游戏
7. 高次剩余问题
    7.1 拉格朗日定理
    7.2 二次剩余
        7.2.1 定义与符号
        7.2.2 二次剩余的数量
        7.2.3 欧拉判别准则
        7.2.4 Cipolla 算法
        7.2.5 任意模数二次非剩余
        7.2.6 总结
    7.3 高次剩余
    7.4 例题
        I. P5491 【模板】二次剩余
        *II. P6610 [Code+#7]同余方程
8. 卢卡斯定理
    8.1 定理介绍
    8.2 扩展卢卡斯定理
    8.3 例题
        I. P3807 【模板】卢卡斯定理
        *II. [BZOJ2445]最大团
        III. P4720 【模板】扩展卢卡斯定理/exLucas
9. 结语
10. 参考资料
__EOF__
本文作者： Alex_Wei
本文链接： https://www.cnblogs.com/alex-wei/p/Number_Theory.html
关于博主： I am a good person
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

CHANGE LOG

0. 前置知识

0.1 基本定义与记号

0.2 费马小定理

0.3 模意义下乘法逆元

0.4 威尔逊定理

0.5 素数在阶乘中的幂次

0.6 素数在组合数中的幂次

0.7 其它有用的事实

1. 扩展欧几里得算法

1.1 解的存在性

1.2 算法介绍

1.3 解的形式与数值范围

1.4 应用

1.5 例题

I. UVA10104 Euclid Problem

II. P5656【模板】二元一次不定方程 (exgcd)

*III. UVA12775 Gift Dilemma

IV. 某模拟赛 你还没有 AK 吗

*V. P3421 [POI2005]SKO-Knights

*VI. P3518 [POI2011]SEJ-Strongbox

*VII. P7325 [WC2021] 斐波那契

2. 欧拉函数

2.1 定义与性质

2.2 欧拉定理

2.3 线性筛欧拉函数

2.4 例题

I. SP4141 ETF - Euler Totient Function

II. UVA10179 Irreducable Basic Fractions

III. UVA11327 Enumerating Rational Numbers

*IV. P4139 上帝与集合的正确用法

*V. P3747 [六省联考 2017] 相逢是问候

3. 离散对数问题

3.1 大步小步算法

3.2 扩展大步小步算法

3.3 例题

I. P3846 [TJOI2007] 可爱的质数 /【模板】BSGS

II. P2485 [SDOI2011]计算器

III. SP3105 MOD - Power Modulo Inverted

IV. P3306 [SDOI2013] 随机数生成器

4. 线性同余方程组

4.1 中国剩余定理

4.2 扩展中国剩余定理

4.3 例题

I. P1495 【模板】中国剩余定理(CRT)/曹冲养猪

II. P4777 【模板】扩展中国剩余定理（EXCRT）

III. P4774 [NOI2018] 屠龙勇士

IV. P4621 [COCI2012-2013#6] BAKTERIJE

V. P2480 [SDOI2010]古代猪文

5. 数论分块

5.1 算法介绍

5.2 扩展

5.2.1 向上取整

5.2.2 高维数论分块

5.3 例题

I. 某模拟赛 你还没有卸载吗

II. *CF1603C. Extreme Extension

III. P2260 [清华集训2012]模积和

6. 阶与原根

6.1 阶

6.2 原根

6.3 相关应用

6.4 例题

*I. P5605 小 A 与两位神仙

*II. P6730 [WC2020] 猜数游戏

7. 高次剩余问题

7.1 拉格朗日定理

7.2 二次剩余

7.2.1 定义与符号

7.2.2 二次剩余的数量

7.2.3 欧拉判别准则

7.2.4 Cipolla 算法

7.2.5 任意模数二次非剩余

7.2.6 总结

7.3 高次剩余

7.4 例题

I. P5491 【模板】二次剩余

*II. P6610 [Code+#7]同余方程

8. 卢卡斯定理

IV. 某模拟赛你还没有 AK 吗

I. 某模拟赛你还没有卸载吗