当前位置：首页 > news >正文

别光背模板了！通过三道经典数论题（洛谷P3383、P3811、P1495），深入理解同余与逆元的本质

news 2026/4/17 16:14:53

三道经典数论题背后的思维跃迁：从模板套用到本质理解

很多算法竞赛选手在刷题时容易陷入"背模板"的误区——看到题目先想有没有现成算法可用，而忽视了对其数学本质的思考。这种学习方式在面对简单题目时或许有效，但遇到变体或综合题就会束手无策。本文将通过对洛谷P3383（线性筛素数）、P3811（线性求逆元）和P1495（中国剩余定理）这三道经典数论题的深度剖析，揭示同余与逆元背后的数学本质，帮助读者建立真正的数理思维。

1. P3383线性筛素数：筛法背后的数学结构

素数判定与筛法是数论最基础的内容，但很多人只是机械地记住了埃拉托斯特尼筛法和欧拉线性筛的代码模板，却不理解其优化本质。让我们从最基本的素数定义出发：

素数的数学定义：大于1的自然数，除了1和它本身外没有其他正约数。

1.1 暴力筛法的局限性

最直观的素数判定方法是试除法：

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True

这种方法的时间复杂度是O(√n)，当需要判断大量数字时会非常低效。例如判断1e6以内的所有素数，时间复杂度高达O(1e9)。

1.2 埃拉托斯特尼筛法的优化思想

埃筛的核心思想是"标记合数"而非判断素数：

def eratosthenes(n): sieve = [True] * (n+1) sieve[0] = sieve[1] = False for i in range(2, int(n**0.5)+1): if sieve[i]: for j in range(i*i, n+1, i): sieve[j] = False return sieve

关键优化点：

从i²开始标记，因为小于i²的合数已经被更小的素数标记过
外层循环只需到√n，因为更大的数的倍数会超出范围

时间复杂度为O(n log log n)，空间O(n)。这已经是不错的改进，但它仍有重复标记的问题——例如数字6会被2和3都标记一次。

1.3 欧拉线性筛的突破

欧拉筛的核心改进是确保每个合数只被其最小质因数标记一次：

def euler_sieve(n): primes = [] is_prime = [True] * (n+1) for i in range(2, n+1): if is_prime[i]: primes.append(i) for p in primes: if p * i > n: break is_prime[p * i] = False if i % p == 0: break # 关键点 return primes

理解关键点：

if i % p == 0: break保证了每个合数只被筛一次
当i是p的倍数时，更大的p'*i会被p筛掉（因为p是i的因数）

这种算法的时间复杂度严格O(n)，因为它每个合数只被处理一次。理解这一点需要认识到：每个合数都有唯一的最小质因数，而线性筛正是基于这一性质设计的。

思考题：为什么在线性筛中，当i是p的倍数时需要终止内层循环？如果不这样做会有什么后果？

2. P3811线性求逆元：同余运算的逆思维

逆元是模运算中极为重要的概念，但很多学习者只是记住了费马小定理的公式，却不理解其背后的代数结构。让我们从基础定义出发：

逆元的定义：在模m下，a的逆元x满足a*x ≡ 1 (mod m)，记作a⁻¹。

2.1 费马小定理法的局限性

根据费马小定理，当m为素数且a不被m整除时： a^(m-1) ≡ 1 (mod m) ⇒ a*a^(m-2) ≡ 1 ⇒ a⁻¹ ≡ a^(m-2)

def inv_fermat(a, m): return pow(a, m-2, m)

这种方法简单直接，但有两个限制：

仅适用于m为素数的情况
当m很大时，快速幂仍有一定计算量

2.2 扩展欧几里得算法的普适解法

扩展欧几里得算法可以求解ax + my = 1的整数解，其中x就是a的逆元：

def exgcd(a, b): if b == 0: return a, 1, 0 g, x, y = exgcd(b, a % b) return g, y, x - (a // b) * y def inv_exgcd(a, m): g, x, y = exgcd(a, m) return x % m if g == 1 else None # 无解情况

这种方法适用于任何互素的a和m，但逐个求解1到n的逆元时时间复杂度为O(n log m)。

2.3 线性递推法的精妙设计

对于求1到n所有数模素数p的逆元，存在O(n)的递推方法：

def linear_inv(n, p): inv = [0]*(n+1) inv[1] = 1 for i in range(2, n+1): inv[i] = (p - p // i) * inv[p % i] % p return inv

数学推导：设p = ki + r (r = p % i < i) 则 ki ≡ -r (mod p) 两边乘以inv(i)inv(r): kinv(r) ≡ -inv(i) (mod p) ⇒ inv(i) ≡ -k*inv(r) ≡ (p - k)*inv(r) (mod p) 而 k = ⌊p/i⌋，r = p%i

这个推导展示了如何利用模运算的性质和已计算的小数逆元来推导大数逆元，体现了数论中"以小推大"的典型思维。

3. P1495中国剩余定理：同余方程的系统解法

中国剩余定理(CRT)解决的是同余方程组的求解问题，但很多实现只是套用公式，没有理解其背后的代数原理。

3.1 两个同余方程的简单情况

考虑方程组： x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)

当m₁和m₂互素时，解的形式为： x ≡ a₁ + m₁*(a₂ - a₁)*inv(m₁, m₂) (mod m₁m₂)

def crt2(a1, m1, a2, m2): g, p, q = exgcd(m1, m2) if (a2 - a1) % g != 0: return None # 无解 lcm = m1 // g * m2 x = (a1 + (a2 - a1) // g * p % (m2 // g) * m1) % lcm return x, lcm

3.2 一般情况的推广解法

对于k个同余方程的情况，可以逐个合并：

def crt(equations): # equations: [(a1, m1), (a2, m2), ...] x, lcm = 0, 1 for a, m in equations: g, p, q = exgcd(lcm, m) if (a - x) % g != 0: return None x += (a - x) // g * p % (m // g) * lcm lcm = lcm // g * m x %= lcm return x, lcm

关键点理解：