数论笔记:最大公约数

关于最大公约数的求解，主要有欧几里得算法和Stein算法两种方法。
欧几里得算法

欧几里得算法的原理为：

若

$$a \equiv r(mod\ b)$$
则

$$gcd(a,b) = gcd(b,r)$$

算法执行过程为辗转相除法。

算法实现也很简单：

递归形式：

/**
 * 求解 a, b 两个数的最大公约数。
 */
int gcd(int a, int b)
{
    if(b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

非递归形式：

/**
 * 求解 a, b 两个数的最大公约数。
 */
int gcd(int a, int b)
{
    while(b > 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

欧几里得算法的时间复杂度为
，最坏情形为斐波那契数列的相邻两项。空间复杂度为

Stein算法

Stein算法是另一种求解两个数的最大公约数的算法。其原理为：

Stein算法的实现如下：

/**
 * Stein算法
 *
 * 条件：0 <= b < a.
 */
int gcd(int a, int b)
{
    int r = 0;
    while(b > 0) {
        if(a&0x01 == 0 && b&0x01 == 0) { // a, b 都为偶数
            a >> 1; b >> 1; r = r + 1;
        }
        else if(a&0x01 == 0 && b&0x01 == 1) { // a 偶，b 奇
            a >> 1;
        }
        else if() { // a 奇，b 偶
            b >> 1;
        }
        else if() { // a 奇，b 奇
            a = (a-b) >> 1;
        }

        if(a < b) {
            a ^= b; b ^= a; a ^= b; // swap(a, b);
        }
    }
    return a<<r;
}

与欧几里得算法相比，Stein 算法的优点在于不需要对大整数进行取模运算，只需要进行移位和减法运算。

扩展欧几里得算法

我也是刚刚弄懂,非递归的版本可以去看看资料,里面有

 #include <stdio.h>
 int x,y;
 int egcd(int,int);

 int main(void)
 {
     int a=7,b=5;
     printf("%d",egcd(a,b));
     return 0;
 }

 int egcd(int a,int b)
 {
     if(b==0)
     {
         x=1;
         y=0;
         return a;
     }
     int r=egcd(b,a%b);
     int t=x;
     x=y;
     y=t-a/b*y;
     return r;
 }

资料:
https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
http://www.nowamagic.net/academy/detail/40110168
http://www.nowamagic.net/academy/detail/40110119 这个不错