拓展欧几里得算法与应用

2019-03-03 14:43:55


欧几里得算法

即: $gcd(a,b)=gcd(b,a$ % $b)$

欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法—— $gcd$ 。

说白了就是求最大公约数。一行代码搞定:

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

拓展欧几里得算法

定理

定理1:设 $a$ 和 $n$ 不全为 $0$ ,则存在整数 $x,y$ ,满足 $ax+by=gcd(a,b)$ 。

证明:

当 $b=0$ 时, $gcd(a,b)=a$ 。因为 $1\times a + 0 \times 0 =a$ ,所以, $ax+by=gcd(a,b)$ 有一组解为 $x=1,y=0$ 。

当 $b \not = 0 $ 时, $gcd(a,b)=gcd(b,a$ % $b)$ 。

设 $x',y'$ 满足 $gcd(a,b)=bx'+(a$ % $b)y'=gcd(b,a$ % $b)$ 。

那么, $bx'+(a$ % $b)y'=gcd(a,b)$

即, $bx'+(a-(a/b)\times b )y'=gcd(a,b)$ ,其中 $'/'$ 为整除。

所以, $bx'+ay'-(a/b)\times b \times y'=gcd(a,b)$

即, $ay'+b\times (x'-(a/b)\times y')=gcd(a,b)$

那么可以继续递归拓展欧几里得: $x=y',y=(x'-(a/b)\times y')$ 。

因为欧几里得算法的递归过程,可知定理1成立。

证毕。

Code

void Exgcd(int a,int b,int &d,int &x,int &y){
//求解ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)。
    if(!b) d=a,x=1,y=0;
    else{
        Exgcd(b,a%b,d,x,y);
        int tmp=x;x=y;y=tmp-(a/b)*y;
    }
}

拓展欧几里得算法的应用

问题

求解不定方程 $ax+by=c$ 的所有整数解。

分析

当 $gcd(a,b)$ 整除 $c$ 时该方程有解。

设 $g=gcd(a,b),a'=a/g,b'=b/g$ 。

我们可以用上文的拓展欧几里得算法来求出不定方程 $a'x'+b'y'=1$ 的整数解 $x',y'$ 。 那么

$$a'c'x'+b'c'y'=c'$$

$$a'gc'x'+b'gc'y'=c'g$$

即: $$ac'x'+bc'y'=c$$ 所以 $x_0=c'x',y_0=c'y'$ 是方程的一组解。

因为不定方程 $a'x+b'y=c'→$ 同余方程 $a'x \equiv c'(mod \quad b')$ 。所以 $x$ 为 $mod$ $b'$ 的一个剩余类,所以该补丁方程的通解为: $$x=x_0+b' \times t,y=y_0 -a' \times t,(t \in Z)$$

当 $gcd(a,b)$ 不能整除 $c$ 时,就没有上文求解过程,方程无解。

Code

void Exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    // ax+by=gcd(a,b) : (x,y)
    ll t=0;
    if(b==0) d=a,x=1,y=0;
    else{
        Exgcd(b,a%b,d,x,y);
        t=x;x=y;y=t-(a/b)*y;
    }
}
int a,b,c;
int main(){
    a=read();b=read();c=read();
    int g=__gcd(a,b),a1=a/g,b1=b/g,c1=c/g,x1,y1,d;
    Exgcd(a1,b1,d,x1,y1);
    cout<<x1*c1<<" "<<c1*y1<<endl;
    for(int i=-10000;i<=10000;i++){
        int x=x1+b1*i,y=y1-a1*i;
        cout<<x<<" "<<y<<"\n";
    }
}