最大公约数 & 最小公倍数

最大公约数

辗转相除法

辗转相除法基于如下原理：

两个整数的最大公约数，等于 其中较小的数 和 两数相除余数 的最大公约数

明显可以递归求解，当出现整除（余数为 0）时终止，代码如下：

if(a<b) std::swap(a,b);
int GCD(int a, int b){
    if(!b) return a;
    return GCD(b, a%b);
}

也可改写为循环，代码如下：

int GCD(int a, int b){
    if(a<b) std::swap(a, b);
    while(b>0){
        int tmp=a%b;
        a=b;
        b=tmp;
    }
    return a;
}

更相减损术

两数同为偶则同除 2，否则用大数减小数，得到差，用 差 和 减数 重复上面的过程，直到两数相等

int GCD(int a, int b){
    while(true){
        // a,b 均为偶数，则同除 2
        while((!(a&1))&&(!(b&1))) a>>=1,b>>=1;
        if(a>b) a-=b;
        else if(a<b) b-=a;
        else break;
    }
    return 
}

Stein 算法

高度类似于更相减损术，区别看代码

int GCD(int a, int b){
    while(true){
        // 将偶数除 2 直至变为奇数
        while(!(a&1)) a>>=1;
        while(!(b&1)) b>>=1;
        if(a>b) a-=b;
        else if(a<b) b-=a;
        else break;
    }
    return a;
}

最小公倍数

两数相乘再除两数最大公约数即可

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

评论