扩展欧几里德

 1 /*************************************************************************
 2     > File Name:        extend_gcd.cpp
 3     > Author:         wangzhili
 4     > Mail:           wangstdio.h@gmail.com
 5     > Created Time:   2014年03月17日 星期一 20时47分53秒
 6  ************************************************************************/
 7 #include<iostream>          //求GCD(a, b), 同时求解满足条件的x, y, ax + by = GCD(a, b);
 8 using namespace std;
 9 int extend_gcd(int a, int b, int &x, int &y){
10     if(b == 0){
11         x = 1, y = 0;
12         return a;
13     }else{
14         int r = extend_gcd(b, a%b, y, x);
15         y -= x*(a/b);
16         return r;
17     }
18 }
19 
20 int main(){
21     int a, b, x, y;
22     while(cin >> a >> b){
23         int ans = extend_gcd(a, b, x, y);
24         cout << ans << " " <<  x << " " << y << endl;
25     }
26     return 0;
27 }