数论逆元
数论逆元
欧几里得算法
辗转相除
欧几里得算法的递归实现
int gcd(int a, int b) |
- 今天的内容和欧几里得算法密切相关——
裴蜀（贝祖）定理
贝祖定理，又称为裴蜀定理（Bezouts identity）
定理内容是：
对于任意的不全为0的非负整数对a,b，一定存在整数x,y满足：
\[ a*x + b*y = \gcd(a,b) \]
定理证明：
贝祖定理的证明
要证明：\(a*x + b*y = \text{gcd}(a,b) = d\)(方便后面表示)
回想欧几里得算法的最后一步（\(b==0\)时，\(d=a\)）
\(b==0\) 时，显然：只要\(x=1, y=0\)（可为任意值）即可；
\(b<>0\) 时，假设：\(x_0\)，\(y_0\)是\(b*x + (a\%b)*y = d\) 的解，即：\(b*x_0 + (a\%b)*y_0 = d\) 成立；
根据欧几里得算法（辗转相除法），只要能证明 \(a*x_1 + b*y_1 = d\) 也成立即可（想一下数学归纳法）
类似数学归纳法
\[ b \cdot x_0 + (a \% b) \cdot y_0 = d \]
即： \[ \begin{align*} &b \cdot x_0 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_0 \\ &= a \cdot y_0 + b \cdot \left( x_0 - \left\lfloor \frac{a}{b} \right\rfloor \cdot y_0 \right) \end{align*} \]
令： \[ x_1 = y_0,\ y_1 = x_0 - \left\lfloor \frac{a}{b} \right\rfloor \cdot y_0 \]
则得： \[ a \cdot x_1 + b \cdot y_1 = d = \gcd(a, b) \]
定理得证。
求解x,y
按以上方法
扩展欧几里得算法
int ex_gcd(int a,int b, int &x, int &y){ |
拓展在 \(ax + by = gcd(a,b)\) ，可以求解x,y ；同时求解逆元
时间复杂度：\(O(\log(n))\)
同余
概念引入-同余
设\(m \ne 0\)，若\(m \mid (a - b)\)，即\(a - b = km\)，
则称\(a\)同余于\(b\)模\(m\)，记为
\[ a \equiv b \pmod{m} \]
mod一个数 以后值是一样的
同余的性质
定理：模 \(m\) 的同余关系满足
自反性，即有 \(a \equiv a \pmod{m}\)
对称性，即若 \(a \equiv b \pmod{m}\)，则 \(b \equiv a \pmod{m}\)
传递性，即若 \(a \equiv b \pmod{m}\)，且 \(b \equiv c \pmod{m}\)，则有 \(a \equiv c \pmod{m}\)
定理：若\(a \equiv b \pmod{m}\)，且\(c \equiv d \pmod{m}\)，则
\(a \pm c \equiv b \pm d \pmod{m}\)
\(a * c \equiv b d \pmod{m}\)
注意：除法大多数不满足同余
线性同余方程
概念引入-线性同余方程
- 线性同余方程，也叫模线性方程，是最基本的同余方程，即：\(ax \equiv k \pmod{b}\)，其中a、b、k都为常量，x是要求解的未知数。
- 显然，该方程等价于：\(ax + by = k\)，
- 是不是很面熟？
线性同余方程-相关定理
定理1： 线性同余方程： \(ax \equiv k \pmod{b}\)（即：\(ax + by = k\)） 对于未知量 \(x\) 有解，当且仅当 \(\gcd(a, b) \mid k\) 。
如何证明？
- 充分性证明…（贝祖定理）
一定有解 必要性：提取gcd，发现是因子
线性同余方程-相关定理
定理2：线性同余方程：
\[ax \equiv k \pmod{b}\]
（即：\(ax + by = k\)）或者无解，或者对模\(b\)有\(\gcd(a,b)\)个不同的解。
- 定理3：假设方程\(ax \equiv k \pmod{b}\)有解（即有\(d \mid k\)，其中\(d = \gcd(a,b)\)），\(x_0\)是该方程的任意一个解，则该方程对模\(b\)恰有\(d\)个模\(b\)不同余的解，分别为： \[ x_i = x_0 + i(b/d) \quad (0 \leq i \leq d-1) \] 证明参见P398
逆元：
- 推论： 若 \(ax \equiv 1 \pmod{b}\) 有解，则必须满足：\(\gcd(a,b)=1\)，此时x的解称为a模b的逆。
- 说明： 此时，方程所有的解均模b同余。
扩展欧几里得求 x
例题1
杭电LCY算法培训−例1
- 求关于x的同余方程\(ax \equiv 1(\bmod\ b)\)的最小正整数解。
- 题目来源：NOIP2012−提高组（洛谷P1082）
- 题目分析：直白的线性同余方程问题(\(k{=}1\)的特例)
- 求解算法：扩展欧几里得算法
- 注意事项：如何确保求得的x是最小正整数解？
- \(x=(x\%b + b)\%b;\)
注意：纠错，出题目可以有效提高理解水平
费马小定理
费马小定理（Fermat’s Little theorem）
如果p是一个质数，而整数a不是p的倍数，则有 \[ a^{p-1} \equiv 1 \pmod{p} \]
关于该定理的证明将在后续课程介绍欧拉定理时给出。
和上文逆元定义密切相关，逆元就是 \(a^{p-2}\) （p 一定是质数）
模质数p的逆元
由费马小定理可知，当a不是质数p的倍数时： \[ a^{p-1} \equiv 1 \pmod{p} \] 即： \[ a^{p-1} = a * a^{p-2} \equiv 1 \pmod{p} \] 可以得出：模质数p的意义下，整数a的逆元是\(a^{p-2}\) 。
例题二
强调：有除法时的mod，需要用到逆元
题目分析：
一共n种细菌，第k种细菌m个单位时间后的数量是：
\[ \text{SUM}(k) = k + k^2 + k^3 + \dots + k^m = \frac{k \cdot (k^m - 1)}{k - 1} \]
\[ \begin{align*} \text{SUM}(k) \ \% \ P &= \frac{k \cdot (k^m - 1)}{k - 1} \ \% \ P \\ &= k \cdot (k^m - 1) \cdot (k - 1)^{-1} \ \% \ P \\ &= \big( k \cdot (k^m - 1) \ \% \ P \big) \cdot \big( (k - 1)^{P - 2} \ \% \ P \big) \ \% \ P \\ \end{align*} \]
+快速幂
算法说明： 1、上述推导公式使用了模质数P的逆元公式 \(a^{-1} \equiv a^{p-2} \pmod{p}\) 2、需要使用快速幂运算加快运算速度
线性求逆元
记a的逆元为\(a^{-1}\)，并设\(p = k * i + r\)
则有：\(k * i + r \equiv 0 \pmod{p}\)
两边同乘\(r^{-1}, i^{-1}\)，可得：
\(\quad k * r^{-1} + i^{-1} \equiv 0 \pmod{p}\)
\(\quad i^{-1} \equiv -k * r^{-1} \pmod{p}\)
\(\quad i^{-1} \equiv -\lfloor p / i \rfloor * (p \bmod i)^{-1} \pmod{p}\)
适合场景？
核心代码：
inv[1]=1; |
说明：当p为int内的较大素数，比如\(10^9\!+\!7\)，因为有乘法运算，则此时运算过程中需要使用long long
小结：
扩展欧几里得运用场景：解线性同余方程
逆元的运用场景：当需要进行模运算下的除法操作时
常见求逆元算法的对比： 1、扩展欧几里得算法（通用） 2、费马小定理（P为质数，比赛最常见的情况） 3、线性求逆元（适合求P以内的所有整数对应的逆元） 4、欧拉定理（P不是质数）- 后续课程会讲解