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

[C++竞赛]数论

news 2025/8/3 8:43:48

整除性
- 定义：若 (a = b \times q)（(a, b, q \in \mathbb{Z})，(b \neq 0)），则称 (b) 整除 (a)，记作 (b \mid a)。
- 性质：传递性、线性组合保持整除性等。
最大公约数（GCD）与最小公倍数（LCM）
- 欧几里得算法：高效计算 (\gcd(a, b)) 的递归方法，基于 (\gcd(a, b) = \gcd(b, a \bmod b))。
- 扩展欧几里得算法：求解方程 (ax + by = \gcd(a, b)) 的整数解 ((x, y))，应用于解线性同余方程。
- LCM与GCD关系：(\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)})。
算术基本定理
- 唯一分解定理：任何大于1的整数可唯一分解为质数的幂次乘积，即 (n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k})。
- 应用：求约数个数、约数和、GCD/LCM的质因数分解表示等。

模运算性质
- 基本运算规则：((a \pm b) \bmod m = (a \bmod m \pm b \bmod m) \bmod m)，乘法类似。
- 逆元：若 (ax \equiv 1 \pmod{m})，则 (x) 为 (a) 模 (m) 的逆元，记作 (a^{-1})。存在条件：(\gcd(a, m) = 1)。
线性同余方程
- 形如 (ax \equiv b \pmod{m}) 的方程，解法：
  1. 检查 (\gcd(a, m) \mid b)，否则无解。
  2. 用扩展欧几里得算法求特解，通解为 (x = x_0 + k \cdot \frac{m}{\gcd(a, m)})（(k \in \mathbb{Z})）。
中国剩余定理（CRT）
- 求解同余方程组（模数两两互质）：
  [
  \begin{cases}
  x \equiv a_1 \pmod{m_1} \
  x \equiv a_2 \pmod{m_2} \
  \vdots \
  x \equiv a_k \pmod{m_k}
  \end{cases}
  ]
  解为 (x \equiv \sum a_i M_i M_i^{-1} \pmod{M})，其中 (M = \prod m_i)，(M_i = M/m_i)，(M_i^{-1}) 为 (M_i) 模 (m_i) 的逆元。

素数判定
- 试除法：检查 (2) 到 (\sqrt{n}) 的整数是否整除 (n)，适用于小规模数。
- Miller-Rabin算法：概率性检测，基于费马小定理和二次探测定理，时间复杂度 (O(k \log^3 n))（(k) 为测试轮数）。
素数筛法
- 埃拉托斯特尼筛法：标记合数，时间复杂度 (O(n \log \log n))。
- 线性筛（欧拉筛）：每个合数仅被最小质因子筛除，时间复杂度 (O(n))，可同时求积性函数。
费马小定理
- 若 (p) 为素数且 (\gcd(a, p) = 1)，则 (a^{p-1} \equiv 1 \pmod{p})。
- 应用：快速计算模逆元（当 (p) 为素数时，(a^{-1} \equiv a^{p-2} \pmod{p})）。

常见积性函数
- 欧拉函数 (\varphi(n))：小于 (n) 且与 (n) 互质的数的个数。若 (n = \prod p_i^{e_i})，则 (\varphi(n) = n \prod \left(1 - \frac{1}{p_i}\right))。
- 莫比乌斯函数 (\mu(n))：依据质因数分解的指数性质取值（含平方因子时为0，否则为 ((-1)^k)，(k) 为质因子个数）。
- 约数函数 (\sigma_k(n))：所有约数的 (k) 次幂和（如 (\sigma_0(n)) 为约数个数）。
迪利克雷卷积
- 定义：((f * g)(n) = \sum_{d \mid n} f(d) g(n/d))。
- 性质：积性函数的卷积仍为积性函数。

离散对数问题（BSGS算法）
- 求解 (a^x \equiv b \pmod{p})（(p) 为素数）：Baby-Step Giant-Step算法将问题转化为 (O(\sqrt{p})) 时间复杂度的搜索。
原根
- 定义：若 (g) 模 (m) 的阶为 (\varphi(m))，则 (g) 为模 (m) 的原根。
- 存在性：模 (m) 有原根当且仅当 (m = 2, 4, p^k, 2p^k)（(p) 为奇素数）。

二次剩余
- 定义：若存在 (x) 使得 (x^2 \equiv a \pmod{p})（(p) 为奇素数），则 (a) 为模 (p) 的二次剩余。
Legendre符号
- (\left(\frac{a}{p}\right) = a^{(p-1)/2} \pmod{p})，取值：1（是剩余）、-1（非剩余）、0（(p \mid a)）。
Tonelli-Shanks算法：求解二次同余方程 (x^2 \equiv a \pmod{p}) 的根。

快速幂与矩阵快速幂
- 计算 (a^b \bmod m) 的 (O(\log b)) 方法，应用于大指数运算。
卢卡斯定理（Lucas Theorem）
- 组合数模小素数：(\binom{n}{k} \equiv \prod \binom{n_i}{k_i} \pmod{p})（(n_i, k_i) 为 (n, k) 的 (p) 进制表示）。
Pollard’s Rho算法
- 大整数分解的随机算法，时间复杂度约 (O(n^{1/4}))。