扩展欧几里得 学习报告

预备知识

取模运算

数${a}$对数${b}$取模,等价于数${a}$减去数${a}$除以数${b}$向下取整的商乘上数${b}$的差(好绕啊)。

其实就是下面这个式子:
$${a(mod;b){\Longleftrightarrow}a-{\left\lfloor\dfrac{a}{b}\right\rfloor}\times b}$$
很好理解。

最大公约数

数${a}$,${b}$的最大公约数指同时能够整除${a}$,${b}$的最大的正整数。记为 _gcd(a,b)_。

引子

欧几里得定理

原理

又称辗转相除法,原理是这个式子:
$${gcd(a,b)=gcd(b,a(mod ; b))}$$
可以看出这个式子能够递归求解,递归边界为:
$${b=0}$$

证明

${\forall a,b 且a>b}$

若${b\mid a}$ ,显然有${gcd(a,b)=b}$.

考虑${b\nmid a}$:

不妨设${a=bk+c}$,显然有$a\equiv c\pmod{b}$.

设${d\mid a}$且${d\mid b}$,则${c=a-bk\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k}$

故${d\mid c}$.

故${\forall c\mid a}$且${c\mid b}$,${c\mid a(mod; b)}$.

反过来,设${d\mid b}$ ${d\mid a(mod; b)}$,同样有${\frac{a;mod;b}{d}=\frac{a}{d}-\frac{b}{d}k\frac{a;mod;b}{d}+\frac{b}{d}k=\frac{a}{d}}$.

故${d\mid a}$.

故${gcd(a,b)=gcd(b,a(mod;b))}$.

代码实现

1
int gcd(int a,int b){return b?gcd(b,a%b):a;}

很简单,一行就够了。

扩展欧几里得

用途

解方程${ax+by=gcd(a,b)}$

推导

设${ax_1+by_1=gcd(a,b)}$. ······①

${bx_2+a(mod; b)y_2=gcd(b,a(mod; b))}$ ······②

欧几里得定理
${gcd(a,b)=gcd(b,a(mod; b))}$ ······③

由②③:

${bx_2+a(mod; b)y_2=gcd(a,b)}$ ······④

由①④:

${ax_1+by_1=bx_2+a(mod;b)y_2}$ ······⑤

由取模运算等价形式得:

${a(mod; b)=a-{\left\lfloor\dfrac{a}{b}\right\rfloor}\times b}$ ······⑥

由⑤⑥:

${ax_1+by_1=bx_2+({a-{\left\lfloor\dfrac{a}{b}\right\rfloor}\times b})y_2}$ ······⑦

由⑦移项得:

${ax_1+by_1=ay_2+b(x_2-{\left\lfloor\dfrac{a}{b}\right\rfloor}y_2)}$ ······⑧

可得方程的一组可行解为:

$\begin{cases}{x_1=y_2}\y_1=x_2-{\left\lfloor\dfrac{a}{b}\right\rfloor}y_2\end{cases}$ ······⑨

由⑨得:
${\forall x_n,y_n\ne0}$,${\begin{cases}x_n=y_{n+1}\y_n=x_{n+1}-{\left\lfloor\dfrac{a}{b}\right\rfloor}y_{n+1}\end{cases}}$ ······⑩

即每一个${x,y}$都可由上一层推出.

递归边界为:${b=0}$,此时,x=1,y=0.

代码实现

1
2
3
4
5
void exgcd(int a,int b,int& x,int &y){
if(!b){x=1,y=0;return;}
int g=exgcd(b,a%b,y,x);y-=a/b*x;
return;
}

典例

题目链接:NOIP2012 同余方程

推导过程

不妨将题目中的${ax\equiv 1\pmod{b}}$转化为${ax+by=1}$.

若要求${x}$的最小正整数解,很显然,${y}$为负数.

裴蜀定理:${ax+by=1}$有解,当且仅当${a,b}$互素.

那么,${gcd(a,b)=1}$.

求出了${gcd(a,b)}$,就可以运用exgcd来求解.

需要注意的是,${exgcd}$求出的只是一组可行解,需对解出的${x}$进行调整使其成为最小正整数解.

如何调整?

仅需对x进行增减b的倍数的操作,使其恰大于0.

该操作可以简化为取模运算。

正确性可以这样理解:

因为${a,b}$互素,所以对于${x}$,对其增减任意倍数的${b}$,都能保证${b\mid (1-ax)}$.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
long long a,b,x,y;
void exgcd(long long a,long long b,long long& x,long long &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x);y-=a/b*x;
return;
}

int main(){
scanf("%lld %lld",&a,&b);
exgcd(a,b,x,y);
printf("%d",(x+b)%b);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×