功能：求a和b的最大公约数

传入参数：整数a、整数b

传出参数：a和b的最大公约数

算法1：欧几里得算法

时间复杂度：O(n)

实现原理：

设两数为a、b(a>b），求a和b最大公约数(a，b）的步骤如下：

用b除a，得a÷b=q......r1(0≤r1）。若r1=0，则（a，b)=b；

若r1≠0，则再用r1除b，得b÷r1=q......r2 (0≤r2）.

若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1，……

如此下去，直到能整除为止。其最后一个非零除数即为（a，b）。

实现代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> 
using namespace std;

template <typename T>

T GCD(T a,T b)
{
    if(a < b)
    {
        T temp = a;
        a = b;
        b = temp;
    }
    if(b == 0)
        return a;
    return GCD(b,a%b);
}

int main()
{
    int a = 5,b = 6;
    printf("%d\n",GCD(a,b));
    return 0;
}

时间复杂度：O( log(max(a,b)) )

实现原理：

gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。
gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。

特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中

一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个

偶数和一个奇数的最大公约数时，可以先将偶数除以2。

算法过程：

1、如果An=Bn,那么An(或Bn)*Cn是最大公约数,算法结束
2、如果An=0，Bn是最大公约数，算法结束
3、如果Bn=0，An是最大公约数，算法结束
4、设置A1=A、B1=B和C1=1
5、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
6、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn(很显然啦，2不是奇数的约数)
7、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn(很显然啦，2不是奇数的约数)
8、如果An和Bn都不是偶数，则An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn
9、n加1，转1

实现代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

template <typename T>

T GCD(T a,T b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (~a & 1)
    {
        if (b & 1)
            return GCD(a >> 1, b);
        else
            return GCD(a >> 1, b >> 1) << 1;
    }

    if (~b & 1)
        return GCD(a, b >> 1);

    if (a > b)
        return GCD((a - b) >> 1, b);

    return GCD((b - a) >> 1, a);
}

int main()
{
	int a = 4,b = 6;
	printf("%d\n",GCD(a,b));
	
	return 0;
} 

实现代码：

template <typename T>
T LCM(T a,T b)
{
	return a/GCD(a,b)*b;
}

最大公约数、最小公倍数【数论】