本文共 747 字，大约阅读时间需要 2 分钟。

关键词：最大公约数，辗转相除法，最小公倍数
试题链接：
https://www.nowcoder.com/questionTerminal/cf4091ca75ca47958182dae85369c82c

**

最大公约数

**
问题描述：

思路：
求解最大公约数常常会用到辗转相除法（欧几里得算法），基于定理：
若a,b均为正整数，则gcd(a,b)=gcd(b,a%b)。

具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

可以采用递归的方法求解最大公约数：

    int gcd(int a, int b) {           if(b==0)return a;        else return gcd(a,b%a);    }

解决方案：

class Solution {   public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *     * 求出a、b的最大公约数。     * @param a int      * @param b int      * @return int     */    int gcd(int a, int b) {           if(b==0)return a;        else return gcd(b,a%b);    }};

**

最小公倍数

**
最小公倍数的计算在最大公约数的基础上进行，若a，b的最小公约数为d，则a，b的最小公倍数为ab/d。
需要注意的是，在计算ab时有可能出现溢出的情况，所以更恰当的写法是：
最小公倍数= a/d*b。