欧几里德及其拓展和应用

欧几里德定理求最大公约数：

Datatype Gcd(Datatype  a, Datatype  b){
         return (b == 0 ? a : Gcd (b, a%b));
}

运用的原理为辗转相除

Gcd(a, b) == Gcd (b, a) == Gcd(-a, b) == Gcd(|a|, |b|)

拓展欧几里得定理：
求解方程ax + by = Gcd(a, b);

int Gcd_value = 0, x = 0, y = 0; //Gcd_value为a，b的最大公约数

int exGcd(int a, int b, int &Gcd_value, int &x, int &Y){
        if (b == 0){
             x = 1;
             y = 0;
             Gcd_value = a;
        }
        else{
             exGcd(b, a%b, Gcd_value, x, y);
             int temp = x;
             x = y;
             y = tm - y*(a/b);
        }
}

证明：

当a != 0且b == 0，Gcd(a, b) = a，则ax + by = a ==> x = 1且y =0;

当a*b！= 0时，Gcd(a, b) == Gcd (b, a%b);

则有 ax₁ + by₁ = Gcd(a, b) = Gcd (b, a%b) = bx₂ + (a%b)y₂;

将右边变形：b*x₂ + (a%b)*y₂ = b*x₂ + (a –[a/b]*b)*y₂ = b*x₂ + a*y₂ – b*y₂*[a/b] = a*y₂ + b*(x₂ - y₂*[a/b]);

则有 ax₁ + by₁ = a*y₂ + b*(x₂ - y₂*[a/b]) ==> x1 = y2 且 y1 = x2 - y2*[a/b];

 故采用递归的方法直到找到 b==0 时的情况，即 x_n = 1 且 y_n = 0，然后回溯赋值给x_n-1，y_{n-1，然后继续回溯......直到找到}x_0，y₀ ！

欧几里德及其拓展和应用,布布扣,bubuko.com

欧几里德及其拓展和应用

原文：http://www.cnblogs.com/shengshouzhaixing/p/3570358.html