第1章 数论基础：从最大公约数到快速幂
数论，听起来挺高大上的一个词。其实说白了，就是研究整数之间那些规律性的东西。我在做嵌入式开发那会儿，经常要处理一些加密算法、校验码计算，数论知识几乎是天天用。今天咱们就把这块基础打牢。
1.1 最大公约数与欧几里得算法
最大公约数，英文叫 GCD（Greatest Common Divisor）。两个数的最大公约数，就是能同时整除这两个数的最大正整数。比如 gcd(12, 18) = 6。
怎么求？最经典的方法就是欧几里得算法，也叫辗转相除法。原理很简单：gcd(a, b) = gcd(b, a % b)，一直算到余数为 0 为止。
// 欧几里得算法 - 递归写法
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// 迭代写法，我个人更常用这个
int gcd_iter(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}小提示：递归写法虽然简洁，但深度可能很大。比如 gcd(1, 1000000000) 会递归很多层。我建议在工程代码里用迭代版本，避免栈溢出。
1.2 扩展欧几里得算法
扩展欧几里得算法，是在求 gcd 的同时，还能找到一组整数解 x, y，满足：ax + by = gcd(a, b)。这个在解模线性方程、求模逆元时特别有用。
我记得有一次做 RSA 算法的实现，需要求模逆元，就是用扩展欧几里得搞定的。
// 扩展欧几里得算法
// 返回 gcd(a,b)，同时通过指针返回 x, y 满足 ax + by = gcd(a,b)
int exgcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int g = exgcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return g;
}注意：扩展欧几里得返回的 x 可能是负数。如果你需要正数解，记得做取模调整：x = (x % b + b) % b。我曾经在这里吃过亏，调试了半天才发现是负数导致的 bug。
1.3 最小公倍数
最小公倍数（LCM）和最大公约数有个简单关系：lcm(a, b) = a / gcd(a, b) * b。注意这里先除后乘，可以防止中间结果溢出。
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}你想想看，如果先乘后除，a * b 可能直接爆 int 范围。先除后乘就安全多了。
1.4 素数判定
素数，就是只能被 1 和自身整除的数。判定一个数是不是素数，有几种常用方法。
试除法
最直接的方法，从 2 试到 sqrt(n)。为什么到 sqrt(n) 就够了？因为如果 n 有因子，必然有一个小于等于 sqrt(n)。
int is_prime(int n) {
if (n < 2) return 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}优化小技巧：试除时可以先判断 2，然后从 3 开始每次加 2，只试奇数。这样能省一半时间。
埃氏筛
如果要判断 1 到 N 范围内所有数的素数性，用试除法一个个判断太慢了。埃氏筛的思路是：从 2 开始，把每个素数的倍数都标记为合数。
void eratosthenes(int n, int is_prime[]) {
for (int i = 0; i <= n; i++) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = 0;
}
}
}
}注意这里 j 从 i*i 开始，而不是 2*i。因为 2*i, 3*i 这些已经被更小的素数标记过了。
欧拉筛（线性筛）
埃氏筛有个问题：一个合数可能被多个素数重复标记。比如 12 会被 2 和 3 各标记一次。欧拉筛通过让每个合数只被其最小质因子标记一次，做到了 O(n) 的时间复杂度。
void euler_sieve(int n, int primes[], int *cnt, int is_prime[]) {
for (int i = 0; i <= n; i++) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
*cnt = 0;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes[(*cnt)++] = i;
}
for (int j = 0; j < *cnt && i * primes[j] <= n; j++) {
is_prime[i * primes[j]] = 0;
if (i % primes[j] == 0) break; // 核心：保证每个合数只被最小质因子筛掉
}
}
}嗯，这里要注意 if (i % primes[j] == 0) break; 这一行。它保证了当 primes[j] 是 i 的因子时，更大的 primes[j] 就不会再被用来标记，因为那些合数的最小质因子是 primes[j]，而不是更大的素数。
1.5 模运算与快速幂
模运算在密码学、哈希计算里随处可见。核心性质就三条：
(a + b) % m = ((a % m) + (b % m)) % m(a - b) % m = ((a % m) - (b % m) + m) % m(a * b) % m = ((a % m) * (b % m)) % m
快速幂，就是快速计算 a^b mod m。原理是把指数 b 写成二进制，然后分治计算。比如 3^13，13 的二进制是 1101，所以 3^13 = 3^8 * 3^4 * 3^1。
// 快速幂 - 迭代写法
long long fast_pow(long long a, long long b, long long m) {
long long res = 1 % m;
a %= m;
while (b > 0) {
if (b & 1) {
res = (res * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return res;
}核心要点：快速幂的时间复杂度是 O(log b)，而普通循环是 O(b)。当 b 很大时（比如 10^18），差距是天文数字。
1.6 知识体系总览
下面这张图把本章的知识结构串起来了，你可以对照着复习：
1.7 避坑指南与经验总结
做数论相关的题目，有几个坑我反复踩过，分享给你：
- 溢出问题：乘法运算时，a * b 可能超出 int 范围。我习惯用 long long，或者先转成 long long 再乘。
- 负数取模：C 语言里负数取模结果是负数。比如 -3 % 5 = -3。如果需要正数结果，记得加模数再取模。
- 0 和 1 的处理：素数判定时别忘了 0 和 1 不是素数。gcd(0, a) 的结果是 a，这些边界情况要单独处理。
- 性能陷阱：如果只需要判断少量大数是否为素数，试除法就够了。如果需要批量判断，用筛法。我曾经在需要判断 10^6 个数时用了试除法，跑了 3 秒多，换成埃氏筛后 0.1 秒就出结果了。
我的个人习惯：写数论代码时，我会把 gcd、快速幂这些常用函数封装成工具函数，放在一个单独的 utils.h 里。这样每次写新项目时直接 include 就行，不用重新写。省时省力，还减少 bug。
好了，数论基础就讲到这里。这些算法看着简单，但它们是很多高级算法（RSA、哈希、组合数学）的基石。把这块练扎实了，后面学起来会轻松很多。