浅谈欧几里得 与 扩展欧几里得
灵乌路空
2019-05-15 07:59:50
## $$ \text{ 浅谈欧几里得 与 扩展欧几里得:} $$
$Baka$阿空 实在是太 ⑨了 , 没脑子的他只能整理在这里:
如果以下内容中存在错误 ， 请及时通知博主 ，
博主会非常感谢您的指正 ， 并欢迎您把蠢货博主的头 **拧下来**
于 $2019.5.15$ 创建
于 $2019.5.17$ 修复了 $bug$ , 感谢 @[zZZ_han](https://www.luogu.org/space/show?uid=128119) 的帮助
于 $2019.5.19$ 更新了 **求解同余方程组**
于 $2019.8.09$ 修复了 $bug$ ,并调整了排版
------------
## 目录 :
浅谈欧几里得 与 扩展欧几里得
- 小约定
- 欧几里得定理
- 证明
- 简单应用
- 裴蜀定理
- 欧几里得扩展
- 证明
- 应用
- 解不定方程
- 解同余方程
- 解模的逆元
- 求解同余方程组
------------
$$ \text{从此开始，一个天文单位} $$
$$ \large\downarrow $$
------------
### 在开始前的一些小约定 ~~(因为自己记不住)~~ :
- 下取整: $\lfloor x\rfloor = $不超过 $x$ 的最大整数.
例: $\lfloor 5.5\rfloor = 5$ , $\lfloor -1.5\rfloor = -2$.
- 取模运算: $x \mod p=$ $x$ 除以 $p$ 的余数.简记为: $x \% p$ ；
则: 可以这样表达除法: $a=\lfloor \dfrac{a}{p}\rfloor\times p + a\% p$
其中, $a$ 为被除数 , $p$为除数 , $\lfloor \dfrac{a}{p}\rfloor $ 为商 , $a \% p$ 为余数 。
- 模意义：使用$\pmod p$ , 代表 运算的中间值和答案 都对 $p$ 取模.
------------
## 1.欧几里得定理：
#### $\large \gcd(a,b) = \gcd(b,a\% b)$
#### 当 $b=0$ 时 ,有 $\gcd(a,b)= \mid a\mid$ ;
- 感谢cyh学长 [@King丨帝御威](https://www.luogu.org/space/show?uid=68622) 的证明 :
设 : $a,b$ 的最大公约数为 $c$
**则 :** $a=nc\ ,\ b=mc$ , $(n,m \in Z)$ ,
设$a=k\times b + r$
**则 :** $r=a\%b=a-k b=nc-kmc=(n-km)c$
若要使 $\gcd(a,b) = \gcd(b,a\%b)$ ,
则需要证 : $b , r$ 的最大公约数也为 $c$ ,
**即 :** $b=m\times c , r=(n-km)\times c$ 中 , $m , (n-km)$ 互质 。
- 子证明：
用反证法 , 设存在 $d$ 为 $m,(n-km)$ 的最大公约数，且 $d > 1$。
设 : $n-km=qd$ , $m=pd$ , $(q,p \in Z)$
**则 :** $b = mc = pdc\ $ ,
$\ a=kb+r=kpdc + qdc=dc(kp+q)$
**则 :** $a$ 还存在一个因数为 $dc$ ;
因为 $d>0,c>0$ , 则有: $dc > c$
**此结论与 $a,b$ 的最大公约数为 $c$ 相矛盾**
**故 :** 不存在 $d>1$ 作为 $m,(n-km)$ 的最大公约数
**则 ：** $m,(n-km)$互质 ，子证明成立。
由子证明 ，得: $b=mc , r=(n-km)c$ 中 , $m,(n-km)$ 互质 。
**则： $b$ 与 $r$ 的最大公因数仍为 $c$**
证毕 。
------------
- 应用:
有了以上的知识,我们便可以写出一个求$a,b$ 的 $\gcd(a,b)$ 的函数了
由 欧几里得定理可得 , 可通过递归求得 $\gcd(a,b)$ 的值
递归边界即: 当 $b=0$ 时，$\gcd(a,b)=a$ ;
简单的代码实现:
```cpp
int gcd(int a,int b)
{
if(b)
return gcd(b,a%b);
else
return a;
}
```
也可以写成一行：
```cpp
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
```
------------
## 2. 裴蜀定理:
#### 设 $a,b$ 为不全为 $0$ 的整数 ,
#### 则存在整数 $x,y$ ,使得 $\large ax + by = \gcd(a,b)$ 。
特别地 , $\gcd(a,b)=1$ $\Leftrightarrow$
存在 $x,y \in Z$ , 使: $ax+by = 1$ ;
那么该如何证明 定理的正确性 呢 ? 请继续往下看:
## 3. 扩展欧几里得：
#### 对于不完全为 $0$ 的两个数 $a,b$ , 必然存在 无限个 $x,y$ ,使方程
#### $\large ax + by = \gcd(a,b)$成立
- 证明:
设$a>b$
1.当$b=0 $时 , $\gcd(a,b)=a$ ,此时有唯一的解 : $x=1,y=0$;
2.当$a\times b\not= 0$ 时 ,
(设 $x1,y1$是满足如上情况的一组合法的解 )
根据欧几里得定理 : $ \gcd(a,b) = \gcd(b,a\% b)$ , 可知:
$\large \underline{ax + by }= gcd(a,b) = gcd(b,a\% b)=\underline{b {x1} + (a\% b) y
1}$
**而:** $a\% b = a-\lfloor \dfrac{a}{b}\rfloor \times b$
**则:** 原等式可转化为:
①. $ax + by = bx1 + (a-\lfloor \dfrac{a}{b}\rfloor \times b)y1$
②. $ax + by = bx1 + ay1 -\lfloor \dfrac{a}{b}\rfloor by
1$
③. $ax + by = ay1 +b(x1-\lfloor \dfrac{a}{b}\rfloor y
1)$
**由③，可得：**
$x = y1$
$y=x1- \lfloor\dfrac{a}{b}\rfloor y1 $
**这样** , 就可以得到 $ax+by = c$ 的一组合法解
方程其他整数解 $xi,yi$ 满足 :
$xi = x + \dfrac{b}{gcd(a,b)} \times t $
$yi = y - \dfrac{a}{gcd(a,b)} \times t $
其中 ， $t \in Z$
------------
- 代码实现
要想写一个求解 $ax + by = \gcd(a,b)$ 的程序
通过以上的证明 , 显然 , 可以通过递归实现
递归边界即 :
当$b=0 $时 , $\gcd(a,b)=a$ ,
此时有唯一的解 : $x=1,y=0$;
代码：
```cpp
int exgcd(int a,int b,int d,int &x,int &y)
{
if(!b)
{
x=1 , y=0;
return a;
}
d=exgcd(b,a % b,x,y);
int tmp=x;
x=y , y=tmp-a/b*y;
}
```
------------
- ### 应用:
1. 求解不定方程;
2. 求解同余方程;
3. 求解模的逆元;
4. 求解同余方程组 (扩展中国剩余定理)
- 求解不定方程:
对于不定方程 : $ ax + by = c $ :
根据 扩展欧几里得 , **可知 :**
不定方程 $ax + by = \gcd(a,b)$ , 有无数组解 $x,y$.
**则有 :**
1. 若$ c\% \gcd(a,b) \not= 0 $ , 则原方程无解。
2. 若$c \% \gcd(a,b) = 0$ :
设 $d = \gcd(a,b)$ , **则原方程可转化为 :**
$ a\times (x\times \dfrac{d}{c}) + b\times (y\times \dfrac{d}{c}) =d (= c\times \dfrac{d}{c})$
换元，使 $x1=(x\times \dfrac{d}{c})$ , $y1=(y\times \dfrac{d}{c})$;
得到方程: $ax1 + by1 = d$
解方程: $ax1 + by1 = d$ , 有无数组解 $x1,y1$,
求解出 $x1,y1$ 后 ,
**再转化:** $x=x1 \times \dfrac{c}{d}$ , $y=y1 \times \dfrac{c}{d}$
即可得到原方程 $ax + by = c$ 的解
- 求解同余方程:
[P1082 同余方程](https://www.luogu.org/problemnew/show/P1082)
对于同余方程 : $ax \equiv c\pmod b$ ,
可以转化为 : $ax \%b = c\% b$
**则有:**
$ ax + nb = c + mb $ ， $(m,n \in Z)$
$ax+(n-m)b=c$
设 $y = n - m$
则推出 $ ax +yb = c $
就转化成了 不定方程 求解的问题。
求得 $x,y$ 后 , 所得的 $x$ , 即原方程 : $ax \equiv c\pmod b$ 的解
这样求出来的 $x$ 必然满足方程,但可能不是最小的 正整数 解
若要获得最小正整数解,需要再加这样一步操作:
```cpp
x = (x+b)%b;
```
- 求解模的逆元:
[P3811 【模板】乘法逆元](https://www.luogu.org/problemnew/show/P3811) ~~(但是此题卡扩欧)~~
**也适用于 模数不为质数的情况**
求解 $x \times inv(x) \equiv 1\pmod p$
其中 $x,p$ 都是已知的。
有没有很眼熟 ？
换元 , 使 $a=x , x=inv(x) , c=1$
原方程变为 : $ax \equiv 1 \pmod p$
这就是一个 未知数为 $inv(x)$ , 方程右侧的 $c=1$ 的同余方程 ,
求 $inv(x)$ 的值 , 解出此同余方程即可。
代码实现:
```cpp
#include<cstdio>
int exgcd(int a,int b,int &x,int &y)
{
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y) ;
int tmp=x;
x=y , y=tmp-(a/b)*y;
return d;
}
signed main()
{
int x,y,a,p;
scanf("%d%d",&a,&p);
exgcd(a,p,x,y);
x=(x%p+p)%p;
printf("%d",x);
}
```
如果想学习其他几种求解乘法逆元的方法
可以参考这篇博客:
[题解 P3811 【模板】乘法逆元】-地靈殿-洛谷博客](https://www.luogu.org/blog/koishikoishi/solution-p3811)
---
- 求解同余方程组 (扩展中国剩余定理)
~~咕了好久终于来更新了~~
[P4777 【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.org/problemnew/show/P4777)
- ##### 要解如下的同余方程组 ：
$\begin{cases}x \equiv a_1\pmod {b_1}\\x \equiv a_2\pmod {b_2}\\......\\x \equiv a_n\pmod {b_n}\\\end{cases}$
其中 , $a_i,b_i$为非负整数 ， $b_1,b_2,...,b_n$ 不一定互质
- ##### 求解:
使用 $exgcd$ , 进行同余方程的合并 .
假设已经求出了前 $k-1$ 个方程的解 $\large x_{k-1}$
设 $\large M=lcm_{i=1}^{k-1} bi$ ,
即 $M$ 为前 $k-1$ 个模数 $b$ 的最小公倍数
**则 :**
对于前 $k-1$个方程, 都满足$\large x_{k-1}+tM\equiv a_i\pmod {b_i}\ \ (t\in Z)$
即 : 前 $k-1$ 个方程 , 通解为 $\large x_{k-1}+tM\ \ (t\in Z)$
欲求得第 $k$ 个方程的解 , 并且将求得的解 , 也满足前 $k-1$ 个方程
**则 :**
需要使第 $k$ 个方程的解 , 为前 $k-1$ 的方程的通解的同时 ， 也满足第 $k$ 个方程的条件 。
设 : 第$k$ 个方程的解 $\large x_k = x_{k-1}+tM\ \ (t\in Z)$
将此解代入第 $k$ 个方程中 , 可得 :
$\large x_{k-1}+tM\equiv a_k\pmod{b_k}$
即 : $\large tM\equiv a_k-x_{k-1}\pmod{b_k}$
其中 : $\large M,a_k,x_{k-1},b_k$ 都是已知的 。
使用 $exgcd$ 解出此同余方程 , 可以得到 $t$ 的值 。
将 $t$ 的值代回 $\large x_k = x_{k-1}+tM\ \ (t\in Z)$ ，就可得到$x_k$的值
进行 $k$ 次上述操作后 ，便可得到 方程组的解 。
贴一下代码:
$ps$ : 原题数据较大,使用了快速乘取余
```cpp
#include<cstdio>
using namespace std;
typedef long long ll;
ll n;
ll a[100010],b[100010];
ll mul(ll A,ll B,ll mod) //快速乘取余 模板
{
ll ans=0;
while(B>0)
{
if(B & 1) ans=(ans+A%mod)%mod;
A=(A+A)%mod;
B>>=1;
}
return ans;
}
ll exgcd(ll A,ll B,ll &x,ll &y) //扩展欧几里得 模板
{
if(!B)
{
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;
}
ll lcm(ll A,ll B) //求最小公倍数
{
ll xxx,yyy;
ll g=exgcd(A,B,xxx,yyy);
return (A/g*B);
}
ll excrt() //重点:求解同余方程组
{
ll x,y;
ll M=b[1],ans=a[1]; //赋初值
//M为前k-1个数的最小公倍数，ans为前k-1个方程的通解
for(int i=2;i<=n;i++)
{
ll A=M,B=b[i];
ll C=(a[i]-ans%B+B)%B; //代表同余方程 ax≡c(mod b) 中a,b,c
ll g=exgcd(A,B,x,y);
//求得A,B的最大公约数，与同余方程ax≡gcd(a,b)(mod b)的解，
if(C%g) return -1; //无解的情况
x=mul(x,C/g,B); //求得x的值,x即t
ans+=x*M; //获得前k个方程的通解
M=lcm(M,B); //更改M的值
ans=(ans%M+M)%M;
}
return ans;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&b[i],&a[i]);
ll ans=excrt();
printf("%lld",ans);
}
```
------------
欢迎转载 , 转载请联系作者 , 并注明出处
~~(虽然这么个小破文肯定不会有人转载的)~~