信竞初等数论导论

引入

如果说数论是数学体系中专门用来研究数字性质的一个分支，那么初等数论则是对整数的性质进行系统性的探讨与研究。千万不要因为其中的“初等”二字小瞧这初等数论尽管名称和学习难度上都没有高等数论那么有逼格，就像初等数学之于高数，数论的所有内容均筑基于此。其中欧几里得证明的算数基本定理（一切合数都可被分解为有限个质数的乘积）在质数筛、GCD（以及LCA)计算、无理数证明等问题上均有用武之地。可以说高等数论奠基于初等数论。它同时也是初学者接触数论的必经之路。

Part1.  前置知识

Div1. 数论有关定理

算术基本定理：每一个合数都可以被分解为有限个质数的乘积。即对于任意合数，都存在：

，其中为质数。

推论一：正整数的正因数集合为：

推论二：正整数的正因数个数为：

推论三：正整数的所有正因数之和为

质数分布定理：区间中，当时，质数个数。

费马小定理： 若是一个质数，则（为同余符号）。

欧拉定理（费马小定理扩展）： 若（与互质），则有，其中为欧拉函数。

Div2. 同余

同余，顾名思义，两个数分别除以一个正整数后得到相同的余数。即。但是它的定义给出了这样一句话：“对于正整数和，若（能被整除），则称和对模同余，记作”。当然以上两种说法是等价的。

同余具有以下三种基本性质：

1. 反身性：对于任何正整数，
2. 对称性：即对于，有
3. 传递性：若，且，有

当然，它可以延申到计算机的模运算（毕竟出现了）。模运算有三种基本运算：

1. 加运算：
2. 减运算：
3. 乘运算：

还有两个推论：

1. 幂运算：
2. 求和运算：

同余消去原则：

若同余号两端的项相等，且都与模互质，则可以同时消去

举例：，如果，则。

Part2.  质数

质数的判断：除了它自身以及以外，不存在其他正整数使得。

Div1.  质数判断

试除法： 这是三种方法中，唯一一种能做到100%正确的质数判断方法。对于给定数，遍历所有间的正整数，若出现则证明它不是质数，因为质数只能被1以及它本身整除。

1
2
3
4
5
6

bool isPrime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

复杂度：

适用范围：普及、提高

试除法の大胜利！

费马素性检验： 是上述费马小定理的实际运用，它与常规算法思想有所不同：它主张在中随机选取一个数。若出现与费马小定理不符的情况，那么一定为合数；若每次均符合定理，称为 费马伪素数 ，因为它很大概率是一个质数。

1
2
3
4
5
6
7
8
9
10
11

bool isPrime(int n) {
	if (n <= 2) return false;
	int k = 10;
	while (k--) {
		srand(time(0));
		int a = rand() % (n - 2) + 2;
		if (__gcd(a, n) != 1) return false;
		if (qpow(a, n - 1, n) != 1) return false; 
	} 
	return true;
}

复杂度：，其中为随机数检验次数，是因为使用了快速幂算法。

适用范围：提高T2及以下（慎用）

为什么用该方法判断的质数 大概率 是个质数呢？不妨测试一下561（3）、1105（5）、1729（7）（括号内为它的最小因子），你会发现函数的返回值均为true，即都为质数。可见这个算法不是100%正确的，这些“漏网之鱼”被称为“Carmichael数”。它们极其罕见，一亿范围内仅255个。也因如此，你可以通过打表特判的方式抠掉这些特例（你保证记得住就行）。2016年中国物流工人余建春给出了一个Carmichael数的判断准则，这个标准目前在国际上得到了广泛认同。

对于优化，你可以在函数起始点加入类似于if (n % 2 == 0 || n % 3 == 0) return false;的特判，进一步降低复杂度。

Miller-Rabin算法： 该算法同样无法保证结果100%准确，慎用！

MB算法实质上是对费马素性检验算法的效率和准确度优化。算法流程如下：

1. 将分解为的形式，其中为奇数
2. 从中选取整数，称为“基数”
3. 计算的值，若结果为或，则可能为质数，继续检验
4. 若结果不等于或，计算、、……的值，若结果等于，则可能为质数，继续检验
5. 若都不等于，则一定是合数。称为强费马证据。

当然，它同样有特例，称为强伪质数，如2047（23）、3277（29）、4033（39）等（括号内为它的最小因子）。

Div2.  质数筛

常见的质数筛法有：试除法、埃氏筛、线性筛。

试除法：从质数定义出发，即存在一个正整数，对于任意间的正整数，总有成立。代码实现只需枚举间所有正整数，并让对其取余。若取模运算出现则代表它不为质数，没有出现则为质数。

1
2
3
4
5
6

bool isPrime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

复杂度：

适用范围：普及T2及以下

这里所展示的试除法代码实际上经过一轮优化。若严格根据质数定义，第二行的循环上限应为。考虑到如下性质：，若，则一定有。因此可以将循环上限压缩至。

埃氏筛：全称叫埃拉托斯特尼筛法，老哥生活在2200年前的古希腊，不借助望远镜就计算出了地球的周长（与真实值偏差仅0.96%）、同时他也是第一位根据经纬线绘制出世界地图的人、也是最先提出将地球根据南北回归线分为“五带”的大人物。他提出的筛法核心思想如下：

第一步：列出从2开始的一列连续数字；第二步：选出第一个质数（本例中为2），将该质数标记，将数列中它的的所有倍数划去；第三步：若数列中的末项小于它前一项的平方，则质数已全部筛出；否则返回第二步。

1
2
3
4
5
6
7
8

void get(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prime[cnt++] = i;
		}
		for (int j = 2; i * j <= n; j ++) vis[i * j] = true;
	}
}

其中，prime数组存储质数，vis数组用于标记（即上文中“划去数字”），变量cnt则存储中质数的个数。

复杂度：

适用范围：普及T2及以下

但是继续观察算法发现：我们其实无需将所有的倍数删去，只需删去前一步得出的质数的所有倍数即可。 这与前文介绍的埃氏法核心相符。因此将循环迁移至条件判断中即可：

1
2
3
4
5
6
7
8

void get(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prime[cnt++] = i;
			for (int j = i + i; j <= n; j += i) vis[j] = true;
		}
	}
}

优化复杂度：

适用范围：普及T3及以下

线性筛/欧拉筛：实质是埃氏筛的线性优化。因为在埃氏筛中，有些数字被重复筛了多次（例如30会被2、3、5筛到）。本着线性优化的原则，我们需要找到一个方法，使得每个合数仅被筛选一次。主要思想如下：

我们发现，线性筛和埃氏筛均使用了质数的倍为合数的结论。我们只需要保证每一个数仅被它自身的最小质因数筛出即可。即对于数字，是一个合数，且只会被筛出。

1
2
3
4
5
6
7
8
9

void get(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prime[cnt++] = j;
		for (int j = 1; prime[j] <= n / i; j++) {
			vis[prime[j] * i] = true;
			if (i % prime[j] == 0) break;
		}
	}
}

复杂度：

适用范围：普及、提高

例题：

1. P5736 【深基7.例2】质数筛
2. P5723 【深基4.例13】质数口袋

Part3.  因数

因数定义： 对于一个数，若存在一个正整数使得，则称是的因数。

Div1.  因数分解法

试除法：万能暴力解法。即遍历间的所有数，若可以整除，则和均为的因数。特殊情况：为整数时，因数仅有本身，因此需特判。

1
2
3
4
5
6
7
8
9
10
11
12

vector<int> get(int n) {
	vector<int> ret;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			ret.push_back(n / i);
		}
		if (n % (i * i) == 0) ret.pop_back();
	}
	sort(ret.begin(), ret.end());
	return ret;
}

复杂度：

适用范围：普及T1

Div2.最大公约数

辗转相除法： 又是我们大名鼎鼎的欧几里得老先生提出的一套公约数算法，整个算极其简洁：核心只有一行，即：

两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

可以写出：

1
2
3

int gcd(int a, int b) {
	return b ? gcd(a, a % b) : a; 
} 

但是为什么呢？我们可以通过以下方法证明：

假设如下关系：。其中被除数，除数，商，余数。则。

首先证明充分性：令、，即二者有相同因子。

代入初始除法算式得：

接着由于加减乘法的封闭性，即一个整数进行加减乘运算得到的结果同样是一个整数。可以得出：。即（）与有共同因子。

接下来证必要性。令、

Stein算法： 上一个方法的明显缺点在于，它处理大质数的效率并不好（但总体来说是很好的），因为它使用了取余运算，这会减慢一些速度。可以理解，生在2000多年前——一个没有电脑和OI的古希腊社会，这个算法已经足够兼顾常规效率和手推难度了。但是步入21世纪，加快的生活节奏毒瘤数据使得人们对更快算法的需求空前高涨。Stein算法便应运而生。

算法流程如下：

1. 任意给定两个正整数，先判断它们是否都是偶数，若是，则用2约简，若不是，则执行第二步。
2. 若两数是一奇一偶，则偶数除以2，直至两数都成为奇数。再以较大的数减较小的数，接着取所得的差与较小的数，若两数一奇一偶，仍然偶数除以2，直至两数都成为奇数。再次以大数减小数。不断重复这个操作，直到所得的减数和差相等为止。
3. 两数相等时，第一步中约掉的若干个2与第二步中最终的等数的乘积就是所求的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int gcd(int a, int b) {
	int p = 0, t;
	if (!(1 & a) && !(1 & b)) {
		a >>= 1;
		b >>= 1;
		p++;
	}
	while (!(1 & a)) a >>= 1;
	while (!(1 & b)) b >>= 1;
	if (a < b) {
		t = a;
		a = b;
		b = t;
	}
	while (a = ((a - b) >> 1)) {
		while (!(1 & a)) a >>= 1;
		if (a < b) {
			t = a;
			a = b;
			b = t;
		}
	}
	return b << p;
} 

这个算法的优点在于：它大大优化了大质数的运算。但可惜的是，它的代码量膨胀了8倍，因此不太建议赛时使用。毕竟C++都给你内置了__gcd()函数嘛，干嘛不偷个懒？

Div3. 最小公倍数

我们可以简单概括成一句话：

两个数的最小公倍数等于这两个数的乘积与这两个数最大公约数的商

即：

凭啥呀？

我们假设两个数和有最大公约数，则，且。并且和一定互质（若不互质，和的最大公约数就不会是，而是一个比大的值）。

由乘法交换律，可知：

消去得：。因为、互质，所以或者即为两个数的最小公倍数。得证。

例题：

1. P1075 [NOIP2012 普及组] 质因数分解
2. P2424 约数和 （需要逆向思维）

Part4. 欧拉函数相关

Div1. 欧拉函数推导

问：论牧师欧拉有多么的高产

答：平均每年800页数学论文你说高不高产嘛

欧拉函数，记作。表示中与互质的数的个数，即，满足的的总个数即为的值。举个例子，，因为在中，和均与互质。特殊地，。

欧拉函数有如下计算公式：若可被表示为（算术基本定理分解式）的形式，则。

推导思想即为用减去所有中所有与不互质的数。在计算机上实现，首先需要分解质因数。思路如下：首先抛出第一个质因数，那么将中所有的的倍数删去，因而可以保证筛出的数一定是的质因子，否则他们将存在最大公约数。那么能被整除的数的个数（也就是以内的倍数个数）为——其中的中括号代表整除。

因此我们离解出欧拉函数就进了一步了，我们的过渡式子就是。

好耶

别急着好耶，我们可以发现一个小小的推导谬误（可能并不是很容易发现）。当我们用去筛数时，使用的算式仍然是。对于形如的数，会被重复筛去多次，导致多减，最终结果会小于。有些抽象，我们来看这张图：

易知中可被整除的数字共有个，能被整除的数字共有个。但是如果说能被和整除的数字共有个，显然不合常理，因为、、都既能被整除，也能被整除，如果不加排除，他们将会被减去2次。因此需要补偿损失，正确的计算方法是（仅计算能被和整除的数的总个数）：

• 能被整除的：个
• 能被整除的：个
• 同时被和整除的：个
• 总个数：个（就是被绿圈和橙圈捆住的的数的个数）

那么对于、、整除问题，中间的被重复加了3次，需减去两次平衡收支。此即容斥原理的简单思想表示。

回到欧拉函数推导上来：过渡公式中的容斥问题可以解决一部分了。对于可同时被两个不同质数整除的数（例如、），我们加上它的总个数。 得到。

当然这又有一个小问题没完没了了是不是？：对于的公倍数，会被先减去3次，然后被上一步的操作加上3次，总体不加不减。还是回到上图：中间的会被每个颜色的圈先减去一次、共3次，上一步的补偿操作，可以看作又被橙绿圈（橙圈和绿圈的交集）、蓝绿圈、蓝橙圈一共加上了3次。减3次加3次相当于没动，为了让它被算上，我们需要加上它，对于则是全部减去（因为括号外有减号需要变号，不要忘记是由一系列不合规的数字个数相减得来的）。得到我们的过渡态3：

又是如上的容斥判断，这里我们省去讨论。将最终的产物合并得到：！（我不会合并，但是你可以把括号拆开看看是不是上述形式。总之，欧拉牛逼！）

，好耶！终于可以好耶了……

Div2. 欧拉函数代码实现

主要是如果压成一个Div会非常的长，因此这里新开一个Div2

我们明确了欧拉函数的推导，接下来就是整理思路写代码的时间了！我们也只需跟着原始思路走就可以了。再次回忆一下：首先我们需要筛出质因数，除去它的所有倍数，再用公式代入就可以了。

1
2
3
4
5
6
7
8
9
10
11

long long eular(int n) {
	long long res = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			res = res * (i - 1) / i;
			while (n % i == 0) n /= i;
		}
	}
	if (n > 1) res = res * (n - 1) / n;
	return res;
}

时间复杂度：

适用范围：All Clear

Div3. 欧拉函数推论

1. 若为质数，则

让我们回到欧拉函数的定义上去：是中与互质的数的个数（特殊地，）。那么对于这个质数，有多少数与它互质呢？

很显然，答案是个！因为的质因子只有本身，若不止一个质因子，很显然它不是一个质数。因此。

2. 假设是一个质数，（或），且的值已知，那么

凭啥呀？

因为已经是一个质数，换句话说：在这个条件下是的一个质因子。在计算时，就已经作为一个质因子以的形式乘进去了。此时可以写作

那么函数值多乘了一个

我们发现：(2)式中包含了(1)式，只是头上乘以了。因而得到

3. 假设是一个质数，（或），且的值已知，那么

这东西长得和性质2很相似，唯一不同的是不再是的一个质因子了。但是变成了的质因子。因此我们计算的值时，不仅需要在头部乘上，而且还需要将乘进去：

因为，所以得到性质3，即。

这三个性质将作为重点性质出现在欧拉函数筛法中。

Div4. 欧拉函数线性筛

我们已经接触了简单的欧拉函数计算方法，那么又该如何解决形如：“给定一个正整数，求的值”的问题呢？

考虑继续使用上面的朴素算法，时间复杂度将会是。明显无法满足需求，更何况，每个数与每个数之间的值之间有一种推导关系，使得我们无需每次重新计算值，而是用已经求出的来线性推出的值。

欧拉函数涉及到质因子的拆分，我们又需要在线性时间内求各种质数。自然而然想到了先前所学的线性筛：

1
2
3
4
5
6
7
8
9
10
11
12
13

int primes[N];
bool st[N];
int cnt = 0;

void sieve(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) primes[++cnt] = i;
		for (int j = 1; primes[j] * i <= n; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

我们运用这段代码可以得出范围内所有的质数，用st[N]数组可以筛出所有的合数。也就是说对于筛出的合数，我们能够得知组成它的质因子是什么，比如st[primes[j]*i]=true;这一行代码。接着套用上述三种性质，我们可以得出值。

此时我们就需要新建一个phi[N]数组来存储每个数的值，并且在代码中三个地方加入对于三种性质的公式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

typedef long long ll;

ll primes[N];
bool st[N];
int cnt = 0;
ll phi[N];

void phi_sieve(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;
			phi[i] = i - 1; 
		}
		for (int j = 1; primes[j] * i <= n; j++) {
			st[primes[j] * i] = true;
			if (i % primes[j] == 0) {
				phi[primes[j] * i] = phi[i] * primes[j];
				break;
			}
			phi[primes[j] * i] = phi[i] * (primes[j] - 1);
		}
	}
}

没错我开了long long防止爆int

时间复杂度：

适用范围：普及&提高

对于开头提出的求和问题，遍历phi[1]到phi[n]的所有值求和即可。

Div5. 欧拉定理

若正整数与互质，则有

对于它的证明，百度百科中如此写到：

取的缩系，故也为的缩系。有

通俗来讲就是这样：

1. 在中取所有与互质的数，很容易知道这样的共有个（根据欧拉函数定义得来）。它们都与互质。
2. 给这列数同时乘上，得到。它们也都和互质，并且各不相同。
3. 提出括号里乘了次的，得到以下关系式：
4. 那么根据同余号两端的消去原则（左右两端两个项相同且与模互质），可以消去。得到，欧拉定理得证。
5. 特殊地，如果是一个质数，有。这被称作费马小定理（先前的费马素性检验就是基于这个原理编写的）。

真不知道明明可以写得通俗点为什么非得省那点空间写看起来那么高深莫测的专业术语，真的是只写给自己看的。

Div6. 降幂算法

尤其对于绿题以上的题目，题面中可能出现“答案可能很大，请对大质数取余”的字样。这意味着题目可能涉及到大规模的幂运算，需要我们用简便的方法计算幂。对于一般的题目，我们使用快速幂。

快速幂：快速幂思想如下：

我们将指数分解为若干的和（二进制表示），例如：，因为。因而不必将连续乘11次，效率大幅提升。

1
2
3
4
5
6
7
8
9
10
11

typedef long long ll;

int qpow(int a, int k, int p) {
	int res = 1;
	while (k) {
		if (k & 1) res = (ll) res * a % p;
		a = a * a % p; 
		k >>= 1;
	}
	return res;
}

时间复杂度：

适用范围：基本All Clear

欧拉降幂：上面方法一个缺点在于无法处理过大的指数，在处理类似于的计算时将会疯狂掉san。接下来介绍一种使用上面讲到的欧拉定理来解决大指数幂运算的方法。

欧拉降幂核心公式：（又称 扩展欧拉定理 ）

也就是说：我们只需要算出的值，再用快速幂算法，将作为新指数带入计算即可。当然，这里的可能会爆long long，因此可以选择使用字符串进行高精度计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

typedef long long ll;

ll primes[N];
bool st[N];
int cnt = 0;

int qpow(int a, int k, int p) {
	int res = 1;
	while (k) {
		if (k & 1) res = (ll) res * a % p;
		a = a * a % p; 
		k >>= 1;
	}
	return res;
}

ll eular(int n) {
	ll res = 0;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;
			res = res * (i - 1) / i;
			while (n % i == 0) n /= i;
		}
		for (int j = 1; i * primes[j] <= n; j++) {
			st[i * primes[j]] = true;
			if (i % primes[j] == 0) break;
		} 
	}
	if (n > 1) res = res * (n - 1) / n;
	return res;
}

int edp(int a, string k, int p) {
	ll phi = eular(p);
	int drop = 0;
	for (int i = 0; i < k.length(); i++) {
		drop *= 10;
		drop += k[i] % phi;
	}
	drop += phi;
	return qpow(a, drop, p);
} 

其中eular(int n)函数用于计算欧拉函数的值、edp(int a, string k, int p)用于计算降幂后的指数、qpow(int a, int k, int p)是快速幂算法。

时间复杂度：