「数论一文通」快速掌握各种OI常用数论操作必看文章!!

「数论一文通」快速掌握各种OI常用数论操作必看文章!!

如此嚣张的题目,我想这次应该有人看了吧.. QAQ

好了,言归正传,既然是一文通,那就不存在 Noip 或者 NOI 或者 省选 的难度划分了,一次性讲完,数论大礼包 (野心之大

如果想更有效率的看下面的文章你可以调杯咖啡 听一下 Axero 的 「Trip」 拿起桌旁的签字笔和草稿纸,一起来探索数论的天地吧!

因为学习顺序是按照个人喜好来学习的,所以并没有严格的学习方法,请各位读者自行调整 (初学者推荐从上到下跟着学)

基础知识

%运算

在数论中,我们会常常用到 % 这种运算符(中文读法 )(正规写法 mod),那这个是什么意思呢,假设我们有两个数,5 与 2, 我们将 5 说成 模数, 2 说成 被模数,然后我们还有另外两个数,分别是 5 与 2,这里的 5 和 2 是和前面的不同的,这里的 5 是 除数, 2 是 被除数, 根据小学知识, 5 / 2 = 1 …. 1 即此形式可以写为 除数 / 被除数 = 商 … 余数,而此刻我们要学习的是 5 % 2 = 1 此形式可以写为 模数 % 被模数 = 余数(此余数与前面的余数等价)

总结:所以 % 的意思是, a % b = c(c = a / b 的余数)

%运算 满足 (a × b) % n = (a % n × b % n) % n

积性函数

在数论中,我们会在化简中经常遇到一个函数,这个函数是 f(ab) = f(a) × f(b)

那么f(ab) = f(a) × f(b) 分两种情况,情况不同 叫法不同

  • 当任意两个质数满足f(ab) = f(a) × f(b)时,我们称它为 积性函数
  • 当任意两个数满足f(ab) = f(a) × f(b)时,我们称它为 完全积性函数

高中部分数学知识

  • 等差数列 | 等比数列
  • 其他的什么(其实是我还没学到那里,等学到再补吧)
  • 微积分
  • 组合数学

素数

素数: 在小于等于该数的条件下,只有 1 和 它本身能整除的数 比如 13

素数也分为两种素数 一种是偶素数 一种是奇素数 偶素数只有 2, 其余的素数都是奇素数

素数中衍生出来的词语:对于两个数或多个整数的公因数只有 1 的非零自然数。公因数只有 1 的两个非零自然数,叫做互质数 简称 这两个或这多个数 互质

暴力判素数

  • sqrt(n)的时间复杂度
  • $n ^ 2$的时间复杂度

先讲 n ^ 2 时间复杂度的判断方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//不懂的地方请自己钻研,难度在高中以下的我都不会进行讲解
#include <cstdio>

bool Prime(int n) {
if(n == 2 || n == 3) return true;
if(n == 1 || !(n & 1)) return false; //n & 1 的意思等价于 n % 2 即 n不为偶数
for (int i = 2; i < n; i++) {
if(n % i == 0) return false;
} return true;
}

int main() {
static int n;
scanf("%d", &n);
if(Prime(n)) puts("Yes");
else puts("No");
return 0;
}

然后再来看 sqrt(n) 时间复杂度的判断方法

对于一个合数,必定是两个数的乘积,这两个数一个肯定是大于等于根号n,另一个一定是小于等于根号n

于是我们只用判断根号n的范围即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//不懂的地方请自己钻研,难度在高中以下的我都不会进行讲解
#include <cstdio>

bool Prime(int n) {
if(n == 2 || n == 3) return true;
if(n == 1 || !(n & 1)) return false; //n & 1 的意思等价于 n % 2 即 n不为偶数
for (int i = 2; i * i < n; i++) {
if(n % i == 0) return false;
} return true;
}

int main() {
static int n;
scanf("%d", &n);
if(Prime(n)) puts("Yes");
else puts("No");
return 0;
}

Miller_Rabin素数检测

在OI中,我们一个$sqrt(n)$时间复杂度的判断素数的方法足以让我们应付所有的正规考试,但是,技多不压身,此算法在小数据上没比$sqrt(n)$的算法快多少,但是大数据上差距一下就可以体现了 (Miller_Rabin的最差时间复杂度为 $(1 + O(1))log2(n))$ 此算法在卡常的题中应用较灵活,可以根据自身接受能力学习

初学者注意,如果你不学这个算法,请看完下面的两个定理再跳到下面的内容

在了解 Miller_Rabin 之前,我们需要了解两个有关的定理 与 这个算法的一个化简通式

  • 费马小定理
  • 二次探测定理
  • 关于 Miller_Rabin 的化简通式

费马小定理

证明将在文章最末补上,因为全是数学符号的证明对初学者来讲.. 并不友好,想看的小伙伴可以直接跳到文章最末

费马小定理中,对于两个数a, p,若 p 为质数,且 $gcd(a, p) = 1$ (代表的意思为 a, p 互质,互质的意思不了解请复习上面素数的章节,对 $gcd$ 不了解的不要急,后面要讲) 那么就满足,$a^{p - 1}≡1(mod p)$ (这个式子可以理解为 $a^{p - 1} % p = 1 % p$ 这里面的 的意思为 同余,字面意思就是 余数相同

总结:对于两个数a, p,若 p 为质数,且 $gcd(a, p) = 1$ 那么就满足,$a^{p - 1}≡1(mod p)$

注意:如果对于两个数 a, p, $gcd(a, p) = 1$ 且 $a^{p - 1}≡1(mod p)$,我们并不能说 $p$ 为质数

但是,$p$ 还是可能为质数的,且概率较大(计算次数越多,概率越大),所以我们 Miller_Rabin 算法主要依靠的就是这个

二次探测定理

证明将在文章最末补上,因为全是数学符号的证明对初学者来讲.. 并不友好,想看的小伙伴可以直接跳到文章最末

二次探测定理中,对于一个奇素数 p 来说,一定有一个 x 满足 $0 < x < p$, 那么就有方程 $x^{2}≡1(mod p)$ 的解为$x = 1$ 或 $x = -1$,但是因为 x 的定义域为 (0, p) 所以我们 x 就 ≠ -1, 但是又因为 $x = -1$ 等价于 $x = p - 1$,所以我们 x 的解就有 $x = 1$ 或 $x = p - 1$,±1 也称为 1 的平凡平方根

那么根据上面两个定理,我们就能获取到两个有利条件

若给定一个正整数 $n$,让判断 $n$ 是否为质数,我们可以判断 $2^{n - 1}%n$ 是否为 $1$,如果不为 $1$,则 n 为合数,否则 $n$ 可能为质数

反复利用二次探测定理,看是否给定的两个数满足条件

二次探测定理这里节选一段别人博客的样例讲解

我们下面来演示一下上面的定理如何应用在$Fermat$素性测试上。前面说过$341$可以通过以$2$为底的$Fermat$测试,因为$2^340 mod 341=1$。如果$341$真是素数的话,那么$2^170mod 341$只可能是$1$或$340$;当算得$2^170 mod 341$确实等于$1$时,我们可以继续查看$2^85$除以$341$的结果。我们发现,$2^85 mod 341=32$,这一结果摘掉了$341$头上的素数皇冠

地址 : https://blog.csdn.net/pi9nc/article/details/27209455

Miller_Rabin 的化简通式

因为除 $2$ 外的任意质数都是奇质数,所以我们就可以列出一个关于幂的方程式

即 $a^{n - 1} = a^{2^{s}} * d$

即 $n - 1= 2 ^ {s} * d$

为什么会出现这个式子?怎么推的?

理由:因为我们要用到 二次探测定理 所以我们需要尽可能的提取因子 $2$

怎么推的:因为任意一个偶数都能分解为$2^{s} * d$的形式 所以就这么推出来的咯

那么根据上面的两个定理和一个化简通式我们就能得到

注意,这里的mul 和 mull 分别是快速幂的两种操作 mul是快速计算$(a * a) % p$ mull是快速计算$(a ^ a) % p$

快速幂将在后面的文章中讲到

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
44
45
46
47
48
49
//#define fre yes

#include <cstdio>
#include <cstdlib>
#include <iostream>

long long mul(long long a, long long b, long long p) { //(a * b) % p
long long ans = 0;
for (long long i = b; i; i >>= 1) {
if(i & 1) ans = (ans + a) % p;
a = (a + a) % p;
} return ans;
}

long long mull(long long a, long long b, long long p) { //(a ^ a) % p
long long ans = 1;
for (long long i = b; i; i >>= 1) {
if(i & 1) ans = mul(ans, a, p);
a = mul(a, a, p);
} return ans;
}

bool Miller_Rabin(long long n) {
if(2LL == n || 3LL == n) return true;
if(n == 1LL || !(n & 1)) return false;

long long s, d, a;
for (s = 0, d = n - 1LL; !(d & 1); s++, d >>= 1); // 计算n - 1 = 2^s * d
for (int i = 0; i < 10; i++) {
a = rand() % (n - 1) + 1; //取 1 ~ n - 1中的任意一个数
long long x = mull(a, d, n); //计算a^d % n
for (int j = 0; j < s; j++) { //看下面那个注释
long long y = mul(x, x, n);
if(y == 1 && x != 1 && x != n - 1) return false;
x = y; //因为二次探测定理是逆向 所依向高次叠加
}

if(x != 1) return false; //这里x必须为1 不然就是false
} return true;
}

int main() {
long long n;
scanf("%lld", &n);
if(Miller_Rabin(n)) {
puts("YES");
} else puts("NO");
return 0;
}

线性筛求素数(欧拉筛)

用O(n)的时间筛出 1 ~ n 中的所有质数

本章始终贯彻的口诀:一初二循三判四循五判六赋七判

欧拉筛的基本框架如此,因为原理方格模拟可证,这里只放出如何记忆和使用 理解

一初

设置初值 NotPrime[1] = 1 即,1 为合数

二循

for (int i = 2; i <= n; i++) (如此)

三判

if(!NotPrime[i]) Prime[++tot] = i;

四循

for (int k = 1; k <= tot; k++)

五判

if(Prime[k] * i > n) break;

六赋

NotPrime[Prime[k] * i] = 1;

七判

if(i % Prime[k] == 0) break;

合在一起即使我们的线性筛素数模板

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
//#define fre yes

#include <cstdio>

const int MAXN_INT = 1000005;
int NotPrime[MAXN_INT], Prime[MAXN_INT];

int tot = 0;
void Prime_Steve(int n) {
NotPrime[1] = 1;
for (int i = 2; i <= n; i++) {
Prime[++tot] = i;
for (int k = 1; k <= tot; k++) {
if(i * Prime[k] > n) break;
NotPrime[i * Prime[k]] = 1;
if(i % Prime[k] == 0) break;
}
}
}

int main() {
static int n;
scanf("%d", &n);
Prime_Steve(n);
for (int i = 1; i <= n; i++) {
if(NotPrime[i] == 0) {
printf("%d\n", i);
}
} return 0;
}
0%