题目链接:B3634 最大公约数和最小公倍数

求最大公约数需要用辗转相除法.例如找24和16的最大公约数

16%24=0......16

24%16=1......8

16%8=2......0

8%0=?

就是拿一个数当除数,一个数当被除数,谁在前都无所谓,如果前面的小,第二轮也会替换位置的,然后被除数除以除数得到一个商和余数,然后再拿除数除以余数,再得到一个商和余数.以此类推,直到余数为0,此时的除数就是我们要求的最大公约数.

然后求最小公倍数就很简单了,一个公式就搞定

$\operatorname{lcm}(a,b)=\frac{|a\times b|}{gcd(a,b)}$​

代码如下

python代码:

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return int(abs(a*b)/gcd(a,b))
a,b=map(int,input().split())
print(gcd(a,b),lcm(a,b))

cpp代码如下:

#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << " " << lcm(a, b);
}

其中cpp代码还是需要使用long long类型的,求lcm的时候有$a\times b$,是有可能溢出的.然后python和cpp我使用了不同的写法.可以用while循环来求gcd,也可以用递归的方式来求gcd.