拓展欧几里得算法与应用

欧几里得算法

即：gcd(a,b)=gcd(b,a%b)欧几里得算法在oi里非常常用，几乎每个数学题都有欧几里得算法——gcd。说白了就是求最大公约数。一行代码搞定：

代码语言：javascript复制

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。因为1times 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’ btimes (x’-(a/b)times y’)=gcd(a,b)那么可以继续递归拓展欧几里得：x=y’,y=(x’-(a/b)times y’)。因为欧几里得算法的递归过程，可知定理1成立。证毕。

Code

代码语言：javascript复制

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的所有整数解。

分析

。那么

a’c’x’ b’c’y’=c’

a’gc’x’ b’gc’y’=c’g

即：

ac’x’ bc’y’=c

所以的一个剩余类，所以该补丁方程的通解为:

x=x_0 b’ times t,y=y_0 -a’ times t,(t in Z)

当

Code

代码语言：javascript复制

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

海外加速编程算法

0 人点赞