扩展欧几里得算法

gcd(a,b) = a * x + b * y;

 

根据数论知识，这样的 x 和 y 一定存在

 

因为：

 

gcd(a,b) = gcd(b,a%b) = b * x' + (a%b) * y'  ;

 

所以：

 

gcd(a,b) = b * x' + (a - b*a/b)*y' = a * y' + b* (x' - a/b * y');

 

所以：

 

x = y'

 

y = (x' - a/b * y')

 

递推至底部时：

 

b = 0 , 此时 a 为 最大公约数，

 

则有：

 

gcd(a,0) = a * 1 + 0 * 0;

 

则递推底部解有：

 

x = 1 , y = 0

 

然后再向上回带即可求解。 

 

#include <cstdlib>
#include <iostream>

using namespace std;

//q用来存储最大公约数 
int x,y,q;
int extend_Euclid(int a,int b){
    if(b==0){
        q = a;
        x = 1;
        y = 0; 
        return a;
    }else{
    extend_Euclid(b,a%b);
    int temp =x ;
    x = y;
    y = temp - a/b*y;
    }
    } 

int main(int argc, char *argv[])
{   int a = 400;
    int b = 456;
    extend_Euclid(a,b); 
    cout<<q<<" = "<<x<<" * "<<a<<" + "<<y<<" * "<<b<<endl;
    cin.get();
    return EXIT_SUCCESS;
}

输出结果：