欧几里得算法与最大公约数

gcd()函数可以算a,b的最大公约数

extend_euclid()函数可以求解a*x+b*y=gcd(a,b)中的x,y

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

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

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

int main()
{
    int x,y;
    int a,b;
    a=435;
    b=400;
    x=0;
    y=0;
    int d = extend_euclid(a,b,x,y);
    int d2=gcd(a,b);
    printf("gcd(a,b)=%d\n%d*(%d)+%d*(%d)=%d",d2,a,x,b,y,a*x+b*y);
}