Exgcd

Exgcd–扩展欧几里得算法

用来求一组$(x,y)$使
$$\begin{array}{}\text{(1)}& ax+by=gcd(a,b)\end{array}$$
我们不难发现
$$\begin{array}{}\text{(2)}& gcd(a,b)=gcd(b,amodb)\end{array}$$
$$\begin{array}{}\text{(3)}& amodb=a-\lfloor \frac{a}{b}\rfloor b\end{array}$$

设一组$(x_1,y_1)$使得
$$\begin{array}{}\text{(4)}& b{x}_1+(amodb)y_1=gcd(b,amodb)\end{array}$$

由上式可得
$$\begin{array}{}\text{(5)}& ax+by=b{x}_1+(amodb)y_1\end{array}$$
整理可得
$$\begin{array}{}\text{(6)}& ax+by=a{y}_1+b(x_1-\lfloor \frac{a}{b}\rfloor y_1)\end{array}$$
会发现一组特解
$$\begin{array}{}\text{(7)}& \{\begin{array}{l}x=y_{1}y=x_1-\lfloor \frac{a}{b}\rfloor y_1\end{array}\end{array}$$
将$x_1,y_1$代回原方程可得
$$\begin{array}{}\text{(8)}& \{\begin{array}{l}{x}_1=y_2{y}_1=x_2-\lfloor \frac{a}{b}\rfloor y_2\end{array}\end{array}$$
发现这是一个递归式

那么边界条件是什么呢?

显然当$a=nb(n\in N^{+})$时$amodb=0$即$y=0$

此时有
$$\begin{array}{}\text{(9)}& ax+0=gcd(a,0)\end{array}$$
因为$gcd(a,0)=a$

故此时我们得到一组解
$$\begin{array}{}\text{(10)}& \{\begin{array}{l}x=1y\in R\end{array}\end{array}$$
将结果返回即可

代码如下

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;
}