文章目录

• 两个数的最大公约数 GCD
• 1.辗转相除法
• 2.内置函数
• 两个数的最小公倍数 LCM
• 多个数的最大公约数
• 多个数的最小公倍数

两个数的最大公约数 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;
}

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