扩展欧几里得算法+推论

什么是扩展欧几里得？

扩展欧几里得算法是建立在欧几里得算法(gcd)之上。

首先，我们知道有$a_x+b_y=gcd(a,b)$

我们怎么求这个$x,y$呢？这时候我们就得使用exgcd算法，我们来推导一下吧！

$ax+by=gcd(a,b)$

$ax+by=gcd(b,a% b)$

$ax+by=bx’+(a- \left \lfloor \frac{a}{b} \right \rfloorb)*y’$

$ax+by= ay’+b(x’-\left \lfloor \frac{a}{b} \right \rfloor*y’)$

因此，根据系数对应，我们得到了 $x=y’$,$y=x’-\left \lfloor \frac{a}{b} \right \rfloor*y’$

那这个式子我们显然可以在递归里面顺带算出来嘛。

再想一想，我们gcd的递归出口为$b=0$，即$a*x=gcd(a,b)$,所以说我们的$x,y$的递归出口也为$x=1,y=0$ 代码大概长这样qwq：

long long exgcd(long long A,long long B,long long &x,long long &y)
{
    if(B==0) 
    {
        x=1,y=0;
        return A;
    }
    long long t=exgcd(B,A%B,x,y),tx=x;
    x=y;
    y=tx-(A/B)*y;
    return t;
}

酱紫，我们就求出了$x,y$的一组解$x_0,y_0$

进一步推导

如果我们要求$x$的最小正整数解，那不免要求$x$的通项公式。

首先我们的推导建立在已经求出了一组$(x_0,y_0)$使得$a\times x+b\times y=gcd(a,b)$

我们要求的$x$的通项公式是建立在$x_0$之上的，我们假设$x=x_0+p$，$y=y_0-q$

现在问题就变为了如何求这个$p$。原式变为：

$$a(x_0+p)+b(y_0-q)=gcd(a,b)$$

展开得：

$$a_{x_0}+a_p+b_{y_0}-q_b=gcd(a,b)$$

与原式$a_{x_0}+b_{y_0}=gcd(a,b)$相减得

$$ap=bq$$

$$p=\frac{b*q}{a}$$

我们设$d=gcd(a,b)$，有$a=a’_d$,$b=b’_d$

将上一个式子上下同时除以$d$得

$$p=\frac{b’*q}{a’}$$

因为$p$为正整数，因此我们的$q$至少等于$a’$才能使得$p$的取值最小

$$p=b*\frac{a’}{a}=b*\frac{1}{d}=b*\frac{1}{gcd(a,b)}$$

解毕，我们得到了$x$的通项公式$x=x_0+k*\frac{b}{gcd(a,b)}$ .

完结撒花(*´ﾟ∀ﾟ｀)ﾉ