洛谷 B3634：最大公约数和最小公倍数 ← 辗转相除法

​【题目来源】
https://www.luogu.com.cn/problem/B3634

【题目描述】
给定两个正整数 a,b，求他们的最大公约数（gcd）和最小公倍数（lcm）。这两个整数 a,b 均在 int 范围内。

【输入格式】
两个整数 a 和 b，用空格分隔。​​​​​​​

【输出格式】
两个整数表示答案，用空格隔开。​​​​​​​

【输入样例】
6 15​​​​​​​

【输出样例】
3 30

【数据范围】
整数 a,b 均在 int 范围内。​​​​​​​

【算法分析】
● 因为 a/gcd(a,b)*b 有可能爆 int，所以需强制转换为 long long 型。
● 辗转相除法，又称欧几里德算法，是求两个正整数之最大公约数的算法‌。它是已知最古老的算法之一，可追溯至公元前 300 年，首次出现于欧几里德的《几何原本》中。该算法基于以下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数，即 gcd(a,b) = gcd(b,a mod b)。

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;int gcd(int a,int b) {if(b==0) return a;else return gcd(b,a%b);
}int main() {int a,b;cin>>a>>b;cout<<gcd(a,b)<<" "<<(LL)a/gcd(a,b)*b;return 0;
}/*
in:6 15
out:3 30
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/B3634
https://blog.csdn.net/hnjzsyjyj/article/details/145671149
 

​