初等数论进阶学习笔记摘要

nbhs23a28 · 2025-07-01 18:16:46 · 算法·理论

声明：本文参考《算法竞赛进阶指南》和《深入浅出进阶篇》结合自己最近学习体验整理，高次同余方程、狄利克雷卷积等内容已超出提高组范畴，在此不做讨论。

质数、约数、整除相关

常用解题思路

倍数法（1 到 n 问题，O(n\log n)（其实筛法就是倍数法应用））；
转化为整除问题数论分块；
转化为互质问题用欧拉函数；
只考虑到数据平方根，或进行分类讨论。
善于转变研究对象，如 abc397_d。

tip：在数论中，O(\sqrt{n}) 复杂度非常重要，不容忽视。

基础知识（入门组算法）

筛质数：埃氏筛（标记质数倍数为合数，O(n\log\log n)），线性筛（累积质因子标记合数，只筛一遍）。
算术基本定理及其组合计数推论（约数个数、和）。

练习：abc400_e，abc383_d。

欧拉函数

欧拉函数用 φ 表示，即 1 至 n 中与 n 互质的数个数，可用质因数分解后容斥得出结论 φ=\sum n(1-\frac{1}p)（p 为质因数分解中的）。

欧拉函数性质：

若 a,b 互质，φ(ab)=φ(a)φ(b)。

欧拉函数应用：

多利用欧拉函数解决互质问题的用途，从 GCD 结果本身出发解决 GCD 相关问题。

例：P2303 Longge 的问题，求 \sum\limits_{i=1}^n \gcd(i, n)。
本题 n<2^{32}，显然的根号算法。由于正整数 n 的正因数个数上界为 2\sqrt{n}（由因数成对），故可以得到解题思路：从对 \gcd 的值 m_i 枚举出发（\gcd 的值只能为 n 的因数），累积计算 1 到 n/m_i 中与 n/m_i 互质的数个数即可。时间复杂度 O(\sqrt{n}\log n)（质因数上界为 \log n，但绝对跑不满）。

练习：P2568 GCD。
在欧拉定理中使用（具体见下文）。

p.s.欧拉函数属于积性函数，有关积性函数内容在此不多加赘述。（可到 oi.wiki 查询）

整除分块

对于任意数 n，n 除以 1 到 n 中的数最多只有 2 \times \sqrt n 种结果（以 \sqrt n 为界两边分别最多有 \sqrt n 种结果）。

应用例：P2261 余数求和（提示：把 \text{mod} 运算展开）。

同余方程与逆元

预备定理：裴蜀（贝祖）定理：整系数不定方程 ax+by=c 有整数解的充要条件是 \gcd(a,b)\mid c。（证明只需等号左边提出 \gcd(a,b)）

求不定方程 ax+by=c 整数解的算法

首先，将问题简化为求 ax+by=\gcd(a,b) 整数解。

本问题可以用扩展欧几里得算法求解。将 a,b 辗转相除，最终得到 \gcd(a,b)·x+0·y=\gcd(a,b)，此时 (0,1) 是一组整数解，接下来往回递归，此时的解变为 (y,x-y\times \frac{a}b),（记上次的解为 (x,y)）。

当 \gcd(a,b)=1 时，本题等效于求 a 在模 b 下的逆元（在组合数计算和有理数（期望等）取模中很有用）。（a 的逆元一般记作 a^{-1}）

求逆元的三种算法

扩展欧几里得算法：同上。
欧拉定理：a^φ ≡ 1(\text{mod }n)，故 a^{-1}=a^{φ-1}（φ 为欧拉函数，见上文），其实质是剩余系（可理解为 φ 个一循环）。
费马小定理：a^{p-1}≡1(\text{mod }p)，故 a^{-1}=a^{p-2}（p 为质数），其实质是欧拉定理特殊情况，可用快速幂求出（在对大质数取模中最常用）。
线性同余方程

模数互质时常见解法：中国剩余定理。（模数不互质可使用 n 次扩欧求公共通解）

对于同余方程组 \begin{cases}x\equiv b_1\pmod{m_1}\\x\equiv b_2\pmod{m_2}\\\dots\\x\equiv b_n\pmod{m_n}\end{cases}（m_1,m_2,\dots,m_n 两两互质），记 m=\Pi_{i=1}^n m_i，M_i=m/m_i，t_i 是 M_i 在模 m_i 意义下的逆元，则原方程组解为 x=\sum\limits_{i=1}^n a_i m_i t_i。

显而易见的证明：其他项对该同余方程不影响，本项中 M_i 与 t_i 在模 m_i 意义上相消。

附：初等数论四大定理：欧拉定理、费马小定理、（中国）剩余定理（孙子定理）、威尔逊定理。
其中威尔逊定理为 (p-1)!+1≡0(\text{mod } p)，其它三种前文均已涉及。