Exgcd

نُشر في عُدل في

Exgcd–扩展欧几里得算法

用来求一组$(x,y)$使
$$
ax+by=gcd(a,b)
$$
我们不难发现
$$
gcd(a,b)=gcd(b,a\quad mod\quad b)
$$
$$
a\quad mod\quad b=a-\lfloor \frac{a}{b} \rfloor b
$$

设一组$(x_1,y_1)$使得
$$
bx_1+(a\quad mod\quad b)y_1=gcd(b,a \quad mod \quad b)
$$

由上式可得
$$
ax+by=bx_1+(a\quad mod\quad b)y_1
$$
整理可得
$$
ax+by=ay_1+b(x_1-\lfloor \frac {a}{b} \rfloor y_1)
$$
会发现一组特解
$$
\begin{cases} x=y_1\ y=x_1-\lfloor \frac {a}{b} \rfloor y_1 \end {cases}
$$
将$x_1,y_1$代回原方程可得
$$
\begin{cases} x_1=y_2\ y_1=x_2-\lfloor \frac {a}{b} \rfloor y_2 \end {cases}
$$
发现这是一个递归式

那么边界条件是什么呢?

显然当$a=nb(n\in N^+)$时$a mod b=0$即$y=0$

此时有
$$
ax+0=gcd(a,0)
$$
因为$gcd(a,0)=a$

故此时我们得到一组解
$$
\begin {cases} x=1 \ y \in R \end {cases}
$$
将结果返回即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int x,y;
void Exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    Exgcd(b,a%b);
    temp=x;
    x=y;
    y=temp-(a\b)y;
}