基础数论

最大公约数 最小公倍数

辗转相除法

先看示例：

x = 5 , y = 7;

max = 7 , min = 5;

7 % 5 = 2;

5 % 2 = 1;

2 % 1 = 0;

那么最大公约数就是1

看到这里大家应该有些眉目了，就是先拿x和y中的max%min , 假如结果为0，那么min就是最大公约数；

否则，temp = max%min, max = min, min = temp;也就是让max=min，min等于刚刚整除的结果；

一直循环下去，直到结果为0，最后的min就是最大公约数；

求最小公倍数lcm：

公式为: x*y/z , z是它们的最大公约数；

那么，最小公倍为：5*7/1 = 35；

// 辗转相除法（自动用最大数 ÷ 最小数） public static int gcd(int a, int b) { // 自动取最大、最小 int max = Math.max(a, b); int min = Math.min(a, b); // 辗转相除核心 while (min != 0) { int temp = min; min = max % min; max = temp; } return max; }

质因数分解

定义：把一个大于 1 的正整数，拆成几个质数相乘的形式，这个过程就叫质因数分解。

先搞懂两个基础词

1. 质数（素数）：除了 1 和它本身，没有其他因数的数。 例：2、3、5、7、11……
2. 因数：能整除这个数的数。

举例子一看就懂

1. 分解 12\(12 = 2 × 2 × 3\) 2 和 3 都是质数，这就是 12 的质因数分解。
2. 分解 18\(18 = 2 × 3 × 3\)
3. 分解 7（本身是质数）质数的质因数分解就是它自己：\(7=7\)

常用方法：短除法（最实用）

用最小的质数不断去除目标数，直到最后结果也是质数，再把所有除数和最后的商连乘。

例：分解 30\(30 ÷ 2 = 15\)\(15 ÷ 3 = 5\)（5 是质数，停止） 结果：\(\boldsymbol{30 = 2 × 3 × 5}\)

小总结

• 分解结果只允许出现质数；
• 写法统一写成质数相乘，相同质数可以写成乘方：\(12=2^2×3\)、\(18=2×3^2\)。

/** * 质因数分解，把所有质因数存到 List 里返回 */ public static List<Integer> getPrimeFactors(int n) { // 创建一个集合用来存质因数 List<Integer> primeFactors = new ArrayList<>(); // 从最小质数 2 开始除 for (int i = 2; i <= n; i++) { // 能整除就一直除 while (n % i == 0) { primeFactors.add(i); // 把质因数存起来 n = n / i; } } // 返回存好的质因数集合 return primeFactors; }

快速幂

快速幂就是：超快算「a 的 b 次方」的算法，不用一遍一遍乘。

1. 普通算法（慢）

算2^100普通写法：2 × 2 × 2 × … × 2（乘 100 次） 问题：次数多了超级慢，比如算2^1亿，根本算不完。

2. 快速幂（快）

把指数拆成 2 的倍数，用「平方」代替「重复乘」次数直接从N 次 → log₂N 次，速度爆炸快。

例子：2^100普通：100 次乘法 快速幂：只需要 7 次

3. 快速幂最常用场景

1. 大数取模（最最重要！） 比如算a^b % mod，数字太大存不下，快速幂能边算边取模，不会溢出。
2. 密码学算法（RSA 等）
3. 矩阵快速幂（递推公式加速）
4. 各种需要高次幂的计算

public static long fastPow(long a, long b) { long res = 1; // 只要指数 b 还没变成 0，就继续循环。 while (b > 0) { // 如果指数是奇数，把当前 a 乘进结果 // 二进制位是1时，把当前的a乘进结果 if (b % 2 == 1) { res = res * a; } // a 不断平方 a = a * a; // 指数除以2 → 右移1位 b = b >> 1; } return res; }

核心原理（一句话）

把指数 b 拆成二进制，只在二进制位是 1 时，把当前的 a 乘进结果；a 每次循环都平方，b 每次都砍半。

互质判断

两个数，除了 1 以外，没有其他共同因数 → 就叫互质。

等价判断：最大公约数 gcd (a,b) = 1 → 互质✅

例子：

• 6 和 7 → gcd=1 → 互质
• 6 和 9 → gcd=3 → 不互质

// 判断 a 和 b 是否互质 public static boolean isCoprime(int a, int b) { return gcd(a, b) == 1; }

欧拉函数 φ(n)

φ(n) = 1 ~ n 中，与 n 互质的数的个数。

比如：

• φ(6) = 2（1、5）
• φ(7) = 6（1~6 都和 7 互质）
• φ(5) = 4

欧拉函数最核心公式

如果 n 质因数分解：n = p₁^k₁ × p₂^k₂ × ... × p_m^k_m

那么：φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ...

例子： n=6 = 2×3 φ(6) = 6 × (1-1/2) × (1-1/3) = 6 × 1/2 × 2/3 =2

Java 求欧拉函数 φ(n)

用质因数分解就能写：

public static int euler(int n) { int res = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { // i 是质因数 while (n % i == 0) { n /= i; } res = res / i * (i - 1); // 欧拉公式核心 } } if (n > 1) { // 剩下一个大质数 res = res / n * (n - 1); } return res; }

阶乘取模

问题特点:

n 稍大，n!就会溢出

解决方法:

边乘边取模即可，不用存完整大数。

基础代码（单个数阶乘取模）

/** * 计算 n! % mod */ public static long factMod(int n, long mod) { long res = 1; for (int i = 2; i <= n; i++) { res = res * i % mod; // 边乘边取模，防止溢出 } return res; }

逆元

定义 ：逆元就是模意义下的倒数

求解方法:费马小定理 ：a 的逆元 = a的(p-2)次方 % p 。代码层面需结合快速幂

1. 普通数学计算 a /b = a × (1 /b) 1/b 是 b 的倒数，除以 b 等价于乘倒数。
2. 模运算存在的问题模运算仅支持加法、减法、乘法，直接做除法会出错。

举例，模数 p=7： 计算 6/3 mod 7 正常结果：6÷3=2，2 mod 7=2 直接对余数相除：(6 mod 7) ÷ (3 mod 7) = 6÷3=2，这一次只是碰巧结果正确。

再看 1/3 mod 7： 整数中不存在小数，模运算也不支持直接做除法，这就是核心问题。

1. 逆元的作用 寻找整数 x，满足 3 × x 除以 7 余 1。 可算出 x=5，5 就是 3 在模 7 下的乘法逆元。

于是： (1 / 3) mod 7 等价于 1 × 5 mod 7 简单说：模运算中，除以一个数，就等价于乘以这个数的逆元，把除法转换成合法的乘法运算。

1. 结合组合数实战理解 组合数公式：C (n,k) = n! ÷ (k! × (n−k)!) 若要求组合数对质数 MOD 取模，原式包含除法，无法直接计算。

转换后公式： C (n,k) mod MOD = n! × inv (k!) × inv ((n−k)!) mod MOD 借助阶乘的逆元，将原式中的除法全部替换为乘法，就能正常运算。

存在条件

逆元存在的前提：除数 b 和模数 p互质（\(\gcd(b,p)=1\)）。算法题常用质数模数，天然满足互质，所以可以用费马小定理快速求逆元。

对比总结

• 普通数学：除以 b → 乘 \(\boldsymbol{\dfrac1b}\)（小数倒数）
• 模运算：除以 b → 乘 \(\boldsymbol{inv(b)}\)（整数逆元）

// a是底数 // b 是次方 p-2 public int fastmi(int a, int b) { int mod = b + 2; int res = 1; while(b > 0) { // 二进制位为1 if(b % 2 == 1) { // 平方 res = res * a % mod; } // 右移一位 b = b>>1; a = a * a % mod; } return res; }

// 用 BigInteger 求逆元，自带快速幂，永不溢出 public static long inv(long x) { BigInteger a = BigInteger.valueOf(x); BigInteger mod = BigInteger.valueOf(MOD); // 费马小定理：x^(MOD-2) mod MOD BigInteger res = a.modPow(BigInteger.valueOf(MOD - 2), mod); return res.longValue(); }

组合

一、基本定义

从 n 个不同元素里，不考虑顺序选出 k 个，总选法数量就是组合数，记作 C (n,k)。 特点：只区分选哪些元素，不区分选取先后。

二、计算公式

规定 0! = 1

三、常用性质

1. C (n,0) = 1：一个都不选，只有 1 种选法
2. C (n,n) = 1：全部选中，只有 1 种选法
3. C (n,k) = C (n,n−k)：选 k 个元素，等价于留下 n−k 个元素，结果一致

四、模运算下的组合数（结合逆元、费马小定理）

1. 问题说明 数字较大时，阶乘结果会溢出，计算时必须取模。但模运算不支持直接做除法，需要用乘法逆元转换。
2. 转换规则 设定模数 p 为质数，根据费马小定理： 数字 x 在模 p 下的逆元 = x^(p−2) 对 p 取模 模运算中，除以一个数，等价于乘以这个数的逆元。
3. 取模公式变形 C (n,k) 对 p 取模 = (n! × k! 的逆元 × (n−k)! 的逆元) 对 p 取模

排列

从 n 个不同元素中，选出 k 个并有序排列