拓展欧几里得-求AX+BY=C中X和Y的值

迈不过友情╰ 2022-07-26 01:49 118阅读 0赞

代码：

/*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：exgcd.cpp
    * 作    者：单昕昕
    * 完成日期：2016年4月2日
    * 版 本 号：v1.0
    */
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    
    ll exgcd(ll m,ll &x,ll n,ll &y) //Extend Euclid
    {
        ll x1,y1,x0,y0;
        x0=1;y0=0;
        x1=0;y1=1;
        ll r=(m%n+n)%n;
        ll q=(m-r)/n;
        x=0;y=1;
        while(r)
        {
            x=x0-q*x1;
            y=y0-q*y1;
            x0=x1;
            y0=y1;
            x1=x;y1=y;
            m=n;n=r;r=m%n;
            q=(m-r)/n;
        }
        return n;
    }
    int main()
    {
        ll a,b,x,y,c;
        cin>>a>>b>>c;//输入三个数
        int A=a,B=b,C=c;
        ll M=exgcd(a,x,b,y);
        if(c%M)
            cout<<"Impossible"<<endl;
        else
        {
            x=x*C/M;
            x=(x%(b/M)+b/M)%(b/M);//x的值
            cout<<"x="<<x;
            y=(C-x*A)/B;//y利用x求出来
            cout<<"  y="<<y<<endl;
        }
        return 0;
    }

测试代码：

/*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：exgcd.cpp
    * 作    者：单昕昕
    * 完成日期：2016年4月2日
    * 版 本 号：v1.0
    */
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    
    ll exgcd(ll m,ll &x,ll n,ll &y) //Extend Euclid
    {
        ll x1,y1,x0,y0;
        x0=1;y0=0;
        x1=0;y1=1;
        ll r=(m%n+n)%n;
        ll q=(m-r)/n;
        x=0;y=1;
        while(r)
        {
            x=x0-q*x1;
            y=y0-q*y1;
            x0=x1;
            y0=y1;
            x1=x;y1=y;
            m=n;n=r;r=m%n;
            q=(m-r)/n;
        }
        return n;
    }
    int main()
    {
        ll a,b,x,y,c;
        cin>>a>>b>>c;
        int A=a,B=b,C=c;
        ll M=exgcd(a,x,b,y);
        if(c%M)
            cout<<"Impossible"<<endl;
        else
        {
            cout<<"a="<<A<<" b="<<B<<" c="<<C<<endl;
            x=x*C/M;
            x=(x%(b/M)+b/M)%(b/M);
            cout<<"x="<<x;
            y=(C-x*A)/B;
            cout<<"  y="<<y<<endl;
            cout<<A*x<<"+"<<B*y<<"="<<C<<endl;
        }
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/f234612079a244a39048847c24e6ce4a.png