学步园

点击打开链接

以下是我自己写的测试程序

/**
*  @author:heiqiaoxiang
*  @time:2013/10/18 19:44
*  @theme:
*/

#include<iostream>
#include<stdAio.h>
#include<math.h>
//#include<algorithm>
#include<string.h>
#include<limits>//numeric_limits
using namespace std;
//#define LOCAL

int gcd1(int a, int b){//递归方法
    //欧几里德算法也称辗转相处法求得a和b的最大公约数
    if(b==0)return a;
    return gcd1(b,a%b);
}
int gcd2(int a, int b){
    //gcd1的简化形式
    return b ? gcd2(b,a%b) : a;
}
int gcd3(int a, int b){//非递归方式即迭代法
    int r;
    while(b != 0){
        r = b;
        b = a % b;
        a = r;
    }
    return a;
}
//对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
/**
证明：设 a>b。

　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

　　2，ab!=0 时

　　设 ax1+by1=gcd(a,b);

　　bx2+(a mod b)y2=gcd(b,a mod b);

　　根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

　　则:ax1+by1=bx2+(a mod b)y2;

　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

     这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

     　  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
*/
int extend_gcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1; y = 0; return a;
    }
    int r = extend_gcd(b,a%b,x,y);
    int t = x; x = y; y = t - (a / b) * y;
    return r;
}
int main(int argc,char const *argv[]){
#ifdef 	LOCAL
    freopen("in.txt","r",stdin);     
#endif
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    printf("a和b的最大公约数：%d %d %d\n",gcd1(a,b),gcd2(a,b),gcd3(a,b));
    printf("a和b的最大公约数：%d %d %d\n",extend_gcd(a,b,x,y),x,y);//注意此处的x和y为初始值，即调用函数extend_gcd之前的值
    printf("x和y：%d %d\n",x,y);
    return 0;

}