欧几里德算法与扩展欧几里德算法

1.欧几里德算法

#include<bits/stdc++.h>

using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
//return b == 0 ? a : gcd(b, a % b);

int main()
{
    int m,n;
    while(cin>>m>>n)
        cout<<gcd(m,n)<<endl;
    return 0;
}

2.扩展欧几里德算法

扩展欧几里德算法顾名思义，是基于欧几里德算法之上的，可以用于求解很多数学问题，下面以计算所有 ax+by=c 符合要求的整数解为例：

#include<bits/stdc++.h>

using namespace std;
int a,b,c,x,y;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){
        x=1;y=0;return a;
    }
    int e=exgcd(b,a%b,x,y);
    int temp=x;x=y;y=temp-a/b*y;
    return e;       
}

int main()
{
    scanf("%d%d%d",&a,&b,&c);
    int k=exgcd(a,b,x,y);   //exgcd返回最大公约数
    if(c%k) cout<<"Impossible"<<endl;
    else{
        x*=c/k;y*=c/k;
        cout<<"x="<<x<<",y="<<y<<endl;        //ax+by=c的一组解
    }
    return 0;
}
/*最小正整数解：
a(x+db) + b(y-da) = c;其中：d=1/k,所以最小正整数解x是：
x*=c/k;t=b/k;则x=(x%t+t)%t；
求出最小x,其对应的y就是(c-a*x)/b。
最小正y也一样；
*/