ユークリッドアルゴリズムを拡張

もっと多くの問題解決報告を見たいです。http://blog.csdn.net/wangjian8006/article/details/7870410                                      転載は出典を明記してください。http://blog.csdn.net/wangjian8006
ユークリッドアルゴリズムは転々相除法で最大公約数を求めます。担当する2つの正の整数a、b、a、bの最大公約数gcd（a、b）を求めます。

         
以上のアルゴリズムの定理は質素なユークリッド定理である：gcd(a，b)=gcd(b，a%b)
ユークリッド定理を拡張する
        完全ではない非負の整数a，bの場合、整数xが存在し、yはgcd(a，b)=a*x+b*yを可能にする。x，yは唯一ではない）。例えば：a=5,b=4gcd(a，b)=gcd(4,5)=1=4*(-1)+5*(1)=4*(4)+5*(-3)
 
xを解いて、yの方法はa>bを設定してもいいです。1,b=0でgcd(a，b)=a。明らかにこの時x=1,y=0；2,a b<>0の場合、a*x 1+b*y 1=gcd（a，b）を2式で成立させることがあります。b*x 2+(a%b)*y 2=gcd(b，a%b)質素なユークリッドの定理によってgcd(a，b)=gcd(b，a%b)があります。
a*x 1+b*y 1=b*x 2+(a%b)*y 2;a%b=a-(a/b)*bは、上式に代入されます。つまり、a*x 1+b*y 1=b*x 2+(a-(a/b)*b)y 2=b*y 2-(a/b)*b*y 2=a*y 2+b*(x 2-(a/b)*y 2)は、恒久的な定理により1=y 1=x 2-(a/b)*y 2これにより、x 1，y 1を解く方法が得られた。x 1，y 1の値はx 2，y 2に基づいている。上の考えは再帰的に定義されている。gcdの再帰的な解法は必ず時間があるので、再帰は終わる。この分析があって、exted_Euclid関数の理解も難しくないです。




ユークリッドテンプレートを拡張すると次のようになります。

int xx,yy;		//        
int gcd(int a,int b){
    if(b == 0) {
        xx = 1;
        yy = 0;
        return a;
    }
    int r = gcd(b, a % b);
    int t = xx;
    xx = yy;
    yy = t - (a/b)*yy;
    return r;
}