欧几里德算法（求最大公约数）

简述

最大公约数Greatest Common Divisor(GCD)算法有好多种，这离我们介绍的是“欧几里德算法”，又名“辗转相除法”

递归定义

两个数的最大公因数 = 它们之中较小的那个数与它们较大的数 mod(取余"%") 较小的数 的最大公因数

即 gcd(a,b) = gcd [min(a,b) , max(a,b) mod min(a,b)]

当a mod b = 0时，b便为我们要找的最大公约数

算法证明

NOIP是不考证明的，有兴趣的童鞋可以了解一下

令a % b = r,
所以a = k × b + r,
所以r = a - k × b
假设d为a，b的一个公约数
那么 d|a， d|b,（d|a的意思就是d整除a，也就是a能被d整除）
所以a - x × b 也一定能被d整除，即 d|r， 也就是 d|(a % b)
d也是b 和 (a % b)的公约数，因此a,b 的公约数和b, (a % b)的公约数也是一样的，其最大公约数也一定相同，所以gcd(a, b) = gcd(b, a % b);

代码实现

非递归版

inline int gcd(int a,int b)
{
    if(a<b) //如果a<b 交换ab的值
    {
        int t=a;
        a=b;
        b=t;
    }
    while(b!=0)
    {
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}

递归版

int gcd(int a,int b)  //调用前预处理如果a<b 交换ab的值 确保a>=b
{
    if(b == 0) return a; //当b = 0时，a便为我们要找的最大公约数 这时返回a的值便可
    return gcd(b,a%b);
}

模板题训练

最大公约数http://codevs.cn/problem/1212/

最大公约数和最小公倍数问题(2001年NOIP全国联赛普及组)https://www.luogu.org/problemnew/show/P1029