两个数的最大公约数 GCD

整数 a 和 b 的最大公约数记为 gcd a , b)

1.辗转相除法

• 递归版

int GCD(int a,int b) { return b == 0 ? a : GCD(b , a % b); } 

短小精悍

• 非递归版

int GCD(int a,int b) { while(b != 0) { int n = a % b;         a = b;         b = n; } return a; } 

时间复杂度差不多是O(log₂n)，非常快了

2.内置函数

• 先引入头文件 #include<algorithm>

std::__gcd(a,b); 

• 内部实现

template<typename EuclideanRingElement> EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) { while (n != 0) {         EuclideanRingElement t = m % n;         m = n;         n = t; } return m; } 

内置的算法跟上面的非递归版一样！

两个数的最小公倍数 LCM

整数 a 和 b 的最小公倍数记为 lcm(a , b)

显然有 gcd(a,b) 整除 lcm(a,b)
那么可以知道 lcm(a,b) = a * b / gcd(a,b)

• 代码

int LCM(int a,int b) { return a * b / gcd(a,b); } 

gcd(a,b)参考前面

多个数的最大公约数

求多个数的最大公约数，考虑到c++的泛型编程，就很容易实现。

具体实现思路为倒着一个一个的求出第一个数的因数，依次拿其余的数除以该因数，若所有的数都能除尽该因数，则该因数即为所求的最大公因数。倒着求因数保证了”最大”。

• 泛型实现求最大公约数

template <typename RAIter> int gcd_s(RAIter _begin, RAIter _end) { bool _isDivisible(true),_flag(false); for(int i = *_begin;i>=2;--i){//倒着求_begin的因数 if(*_begin % i == 0){             _flag = true; for(RAIter _next = _begin+1;_next!=_end;++_next){//依次判断_begin的因数能不能整除其余的数 if(*_next % i != 0){                     _isDivisible = false; break; } } } else             _flag = false; if(_isDivisible && _flag)//若能整除其余的所有数，则该因数即为最大公因数 return i;         _isDivisible = true; } return 1;//所有因数都不满足，说明1是最大公因数 } 

由上面的分析不难看出，每次是求的第一个数的因数，那么如果区间第一个数是所有数里面最小的，那么代码运行速度肯定是最快的，所以使用前让区间第一个数字尽量的小。使用前可以用内置函数 sort() 排一下序

• 使用方法

 vector<int> a{9,108,63,57,12};     array<int,5> b{9,108,63,57,12}; int c[5]{9,108,63,57,12};      cout<< gcd_s(a.begin(),a.end()) <<endl;     cout<< gcd_s(b.begin(),b.end()) <<endl;     cout<< gcd_s(c,c+5) <<endl;//普通数组调法[数组名,数组名+长度)     cout<< gcd_s(begin(c),end(c)) <<endl;//普通数组也可以这样调 

多个数的最小公倍数

考虑两个数的最小公倍数求法，自然想到将所有数乘起来除以最大公约数。但是很遗憾这样并不可行，例如9，10，5的最大公约数为1，而最大公倍数为90 ≠ 9 × 10 × 5 ÷ 1

但是基于这个思路我们可以想到先求出前两个数的最小公倍数，这样问题规模就从n变为n-1，重复这个步骤即可得到最终答案。

• 泛型求最小公倍数

template <typename RAIter> int lcm_s(RAIter _begin,RAIter _end) { int result = *_begin * *(_begin+1) / __gcd(*_begin,*(_begin+1)); for(RAIter _next = _begin+2;_next!=_end;++_next)         result = result * (*_next) / __gcd(result,*_next); return result; } 

调用方法与上面的泛型最大公约数一样。