数论是算法竞赛和面试中的常见考点，涉及：
掌握这几个工具，能解决大量看似复杂的数学问题。
public int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}gcd(a, b) = gcd(b, a % b)public int lcm(int a, int b) {
return a / gcd(a, b) * b; // 先除后乘防溢出
}| 场景 | 用法 |
|---|
交互式动画演示，可调整参数并单步执行。
全屏打开| 分数约分 | 分子分母同除 GCD |
| 周期问题 | 多个周期的公共周期 = LCM |
| 水壶问题 | 能否量出 z 升水 → z % gcd(x,y) == 0 |
public boolean isPrime(int n) {
if (n < 2) return false;
if (n < 4) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; (long) i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}求 [2, n] 内所有素数：
public List<Integer> sieve(int n) {
boolean[] isComposite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) {
primes.add(i);
for (long j = (long) i * i; j <= n; j += i) {
isComposite[(int) j] = true;
}
}
}
return primes;
}每个合数只被其最小质因子筛一次，严格 O(n)：
public List<Integer> linearSieve(int n) {
boolean[] isComposite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) primes.add(i);
for (int p : primes) {
if ((long) i * p > n) break;
isComposite[i * p] = true;
if (i % p == 0) break; // 关键：保证最小质因子
}
}
return primes;
}将指数用二进制表示，逐位处理：
x^13 = x^(1101) = x^8 · x^4 · x^1
public long fastPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = result * base % mod;
}
base = base * base % mod;
exp >>= 1;
}
return result;
}| 场景 | 说明 |
|---|---|
| 大数取模 | a^b % m |
| 矩阵快速幂 | 加速递推（如斐波那契第 n 项） |
| 模逆元 | 费马小定理：a^(p-2) % p（p 为素数） |
(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m // 防负数
注意：除法不能直接取模！需要用模逆元。
当 p 为素数且 gcd(a, p) = 1 时：
a^(-1) ≡ a^(p-2) (mod p)
// 求 a 关于 mod 的逆元（mod 为素数）
long inv = fastPow(a, mod - 2, mod);
// 则 (b / a) % mod = (b * inv) % mod// 预处理阶乘和逆元
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
invFact[n] = fastPow(fact[n], MOD - 2, MOD);
for (int i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
// C(n, k) = fact[n] * invFact[k] * invFact[n-k] % MOD
long comb = fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;| 工具 | 用途 | 复杂度 |
|---|---|---|
| 扩展欧几里得 | 求 ax + by = gcd(a,b) 的解 | O(log n) |
| 中国剩余定理 | 解同余方程组 | O(n log n) |
| 欧拉函数 φ(n) | 计数 [1,n] 中与 n 互质的数 | O(√n) |
| 分解质因数 | 将 n 写成质数之积 | O(√n) |
public Map<Integer, Integer> factorize(int n) {
Map<Integer, Integer> factors = new HashMap<>();
for (int i = 2; (long) i * i <= n; i++) {
while (n % i == 0) {
factors.merge(i, 1, Integer::sum);
n /= i;
}
}
if (n > 1) factors.merge(n, 1, Integer::sum);
return factors;
}long。-7 % 3 = -1，需要 + mod 修正。n = 0、n = 1 时 GCD/素数判定的特殊处理。i * i <= n 用 long 防溢出。