求两个正整数 a,b 的最大公因数与最小公倍数。

两个数的最大公因数指的是 a,b 共有的约数中最大的一个。

两个数的最小公倍数指的是 a,b 共有的倍数中最小的一个。

输入格式:

在一行中给出两个数字 a,b (1<=a,b<=1,000,000,000)

输出格式:

在一行中以空格分隔输出 a,b 的最大公因数与最小公倍数。

输入样例:

1
6 9

输出样例:

1
3 18

思路

​ 根据欧几里德算法或者C++的函数库求出a和b的最大公因数.

​ 最小公倍数则是a*b除以它们的最大公倍数,为了防止a * b计算时由于结果过大而溢出，所以可以先让a除以最大公倍数再乘b

​ 欧几里德算法：设a,b均为正整数，a,b的最大公约数等于b,a%b的最大公约数即Gcd(a,b) = Gcd(b,a % b)

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Gcd(ll a, ll b) {
    return a % b == 0 ? b : Gcd(b, a % b);
}
int main() {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld %lld\n", Gcd(a, b), a / Gcd(a, b) * b);
    return 0;
}
1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long a, b, gcd;
    scanf("%lld %lld", &a, &b);
    gcd = __gcd(a, b);
    printf("%lld %lld\n", gcd, a / gcd * b);
    return 0;
}