GCD和exGCD

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int GCD(int a,int b)//虽然这个没有下面那个GCD简便，但是这个没有爆栈的风险，而且时间和下面那个一样
{
    int temp;
    while(a!=0)
    {
        temp=a;
        a=b%a;
        b=temp;
    }
    return b;
}

/*
int GCD(int a,int b)
{
    return a==0?b:GCD(b%a,a);
}
*/


/*

 扩展欧几里德算法是用来在已知a, b求解一组x、y使得 a*x+b*y = GCD(a, b)  (解一定存在，根据数论中的相关定理)；
 r 是最大公约数。

 */
int exGCD(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exGCD(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int main()
{
    int a,b,x,y;
    while(cin>>a>>b)
    {
        cout<<GCD(a,b)<<endl;
        int r=exGCD(a,b,x,y);
        printf("%d*%d+%d*%d=%d
",a,x,b,y,r);
    }
    return 0;
}