C++ 公约数 公倍数

admin

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}

两个数的最小公倍数即为两数的乘积除它们的最大公约数，
即 lcm(x,y)=x×y/gcd(x,y)