Part 1：前置知识
-
欧几里得算法
\[\forall a,b \in \mathbb{N},\gcd(a,b)=\gcd(b,a \bmod b) \] -
\(\mathrm{Bézout}\) 定理
对于任意整数 \(a,b\)，存在一对整数 \(x,y\)，满足 \(ax+by=\gcd(a,b)\)
证明：
在欧几里得算法的最后一步，即 \(b=0\) 时，显然有一对整数 \(x=1,y=0\)，使得 \(a*1+0*0=\gcd(a,0)\)
若 \(b>0\)，则 \(\gcd(a,b)=\gcd(b,a \bmod b)\)
假设存在一对正整数 \(x,y\)，满足 \(bx_1+(a \bmod b)y_1=\gcd(b,a \bmod b)\)
则有 \(ax+by=bx_1+(a \bmod b)y_1\)
\(\therefore ax+by=bx_1+(a-\left\lfloor\\a/b\right\rfloor*b)y_1\)
\(\therefore ax+by=bx_1+ay_1-(\left\lfloor\\a/b\right\rfloor*b)y_1\)
\(\therefore ax+by=ay_1+b(x_1-\left\lfloor\\a/b\right\rfloor*y_1)\)
\(\therefore x=y_1,y=x_1-\left\lfloor\\a/b\right\rfloor*y_1\)
对欧几里得算法的递归过程应用数学归纳法，可知 \(Bézout\) 定理 成立
利用 \(\mathrm{Bézout}\) 定理，我们就可以使用 扩展欧几里得算法 来求出整数 \(x,y\) 的一组特解
Part 2：扩展欧几里得算法
1、求 \(ax+by=\gcd(a,b)\) 的一组特解
- 代码
#define LL long long
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1; y=0;
return a;
}
LL d=exgcd(b,a%b,x,y);
LL tmp=x;
x=y; y=tmp-(a/b)*y;
return d;
}
2.求 \(ax+by=\gcd(a,b)\) 的通解
-
已知 \(x_0,y_0\) 是一组特解，\(d=\gcd(a,b)\)（下面的 \(d\) 含义相同）
-
那么方程通解为
\[x=x_0+k\dfrac{b}{d}, \qquad y=y_0-k\dfrac{a}{d}\quad(k\in \mathbb{Z}) \]证明：
设 \(x,y\) 是除 \(x_0,y_0\) 之外的一组解则可得：\(\begin{cases}ax_0+by_0=d&(1)\\ax+by=d&(2)\end{cases}\)
\((2)-(1)\) 得：\(a(x-x_0)=b(y_0-y)=\operatorname{lcm}(a,b)*k\)
对 \(a(x-x_0)=\operatorname{lcm}(a,b)*k\) 进行分析：
\(a(x-x_0)=\dfrac{ab}{d}*k\)
\(\therefore x-x_0=\dfrac{b}{d}*k\)
\(\therefore x=x_0+k\dfrac{b}{d}\)
对 \(b(y_0-y)=\operatorname{lcm}(a,b)*k\) 分析，同理可得：\(y=y_0-k\dfrac{a}{d}\)
3.求 \(ax+by=c\) 的解
-
对于一般的方程 \(ax+by=c\)，它有解当且仅当 \(d\mid c\)
-
通过先前的扩欧，我们可以求出方程 \(ax+by=d)\) 的一组特解 \(x_0,y_0\)，然后令 \(x_0,y_0\) 同时乘上 \(c/d\)，就得到了 \(ax+by=c\) 的一组特解：\((c/d)x_0,(c/d)y_0\)
-
由于 \(c\) 是 \(d\) 的倍数，所以类比求 \(ax+by=\gcd(a,b)\) 的通解的过程，我们可以将\(ax+by=c\) 的通解表示为：
\[x=\dfrac{c}{d}x_0+k\dfrac{b}{d}, \qquad y=\dfrac{c}{d}y_0-k\dfrac{a}{d}\quad(k\in \Z) \]
Part 3：乘法逆元
1. 定义
- 若整数 \(a,m\) 互质，且 \(ax \equiv 1 \pmod m\)，那么就称 \(x\) 为 \(a\) 的模 \(m\) 乘法逆元。（记为 \(a^{-1}\)）
2.扩展欧几里得算法求逆元
-
将 \(ax \equiv 1 \pmod m\) 变形可得：\(ax-my=1 \ (m\in\mathbb{Z})\)
-
使用扩欧可轻松求出 \(x\) 的一个特解 \(x_0\)
-
若要求最小最小正整数解，则令 \(x=(x_0 \bmod m+m)\bmod m\)
-
代码
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1; y=0;
return;
}
exgcd(b,a%b,x,y);
int tmp=x;
x=y; y=tmp-(a/b)*y;
return;
}
int main()
{
scanf("%d%d",&n,&m); //n为逆元表达式中的a
int x=0,y=0;
exgcd(n,m,x,y);
x=(x%m+m)%m;
printf("%d\n",x);
return 0;
}
3.费马小定理求逆元
-
前提条件：当 \(m\) 为质数时才可使用
-
前置知识：费马小定理
若 \(p\) 是质数，\(a\) 是正整数，且 \(a\) 不是 \(p\) 的倍数，则 \(a^{p-1} \equiv 1 \pmod p\)
-
已知\(\begin{cases}ax \equiv 1 \pmod m&(1) \\ a^{m-1} \equiv 1 \pmod m&(2)\end{cases}\)，那么由 \((1)(2)\)可推出 \(ax \equiv a^{m-1} \pmod m\)，所以 \(x=a^{m-2}\)
-
一般情况下，我们可以使用快速幂来求出 \(a^{m-2}\)
4.线性递推求逆元
-
当题目需要我们求出一串数字 \(\bmod\) \(m\) 的逆元时，我们会采用这种方式
-
我们记 \(x\) 的逆元为 \(inv[x]\)，已知 \(1*1 \equiv 1 \pmod m\)，所以 \(inv[1]=1\)
-
设 \(m=k*x+r \quad (1 \leqslant r <x<m)\)，也就是说 \(k\) 是 \(m/x\) 的商，\(r\) 是余数。那么就有：
\[k*x+r \equiv 0 \pmod m \]乘上 \(inv[x]*inv[r]\)，就有：
\[k*inv[r]+inv[x] \equiv 0 \pmod m \]\[inv[x] \equiv -k*inv[r] \pmod m \]\[inv[x] \equiv -\left\lfloor\\\dfrac{m}{x}\right\rfloor *inv[m \bmod x] \pmod m \] -
这样，我们就可以线性地递推出乘法逆元。但值得注意的是，一般题目中都要保证求出的逆元是正数，所以我们会在递推时往递推式中加一个 \(m*inv[m \bmod x]\)
-
代码
inv[1]=1;
for(int i=2; i<=n; i++)
inv[i]=(long long)(m-m/i)*inv[m%i]%m;