本文介紹歐幾裡得算法求解最大公因數與最小公倍數問題。
1.最大公因數
最大公因數，也即最大公約數。
最大公約數即為 Greatest Common Divisor，常縮寫為 gcd。
我們求出最大公因數可以用于分數的約分問題，隻要分子、分母都除以最大公因數d。
最常用的求最大公因數的方法時歐幾裡得算法，也即輾轉相除法。時間複雜度為\(O(logn)\)。
歐幾裡得算法基于下面的定理：
設a，b為均正整數，則
gcd(a,b) = gcd(b,a%b)
。
1.1遞歸寫法
// 正常寫法
int gcd(int a,int b){
if (b == 0) return a; // 退出邊界
else return gcd(b,a % b);//遞歸
}
// 簡化寫法
int gcd(int a,int b) {return !b?a:gcd(b,a%b);} // 注意加上{}
1.2循環寫法
int gcd(int a,int b){
int r;
while (b != 0){
r = a%b,a = b,b = r; // 輾轉相除
}
return a;
}
總結：循環寫法相對代碼多一點，但是遞歸寫法記憶體消耗大一點。
個人還是推薦遞歸寫法，畢竟碼字快一點。
tips：這裡要求a>b，但是a<b也能計算，會多遞歸一次，相當于交換。
2.最小公倍數
接下來我們介紹如何求解最小公倍數（Least Common Multiple, LCM）。
我們容易發現，對于兩個正整數a和b，它們的最小公倍數是ab/d(d是最大公因數)。
注意：
為了避免a*b可能存在的溢出問題，我們可以改寫為a/d*b
如果你對詳細證明過程感興趣的話，推薦食用文章：https://oi-wiki.org/math/gcd/。
3.例題
題目連結：C語言網。
題目描述
已知一個正整數N，問從1~N中任選出三個數，他們的最小公倍數最大可以為多少。
輸入
輸入一個正整數N。
1 <= N <= 10^6。
輸出
輸出一個整數，表示你找到的最小公倍數。
題目要求我們在1 ~ N之間任意選擇三個數，使得它們的最小公倍數最大。
要使得最小公倍數最大，那麼思路可以是：
1.這三個數要兩兩互質
2.在滿足1的前提下，使得三個整數取最大值
第一點已經在上面分析過了。而第2點也很好了解，其實就是貪心政策。
-
N為奇數時
當N為奇數時，N - 1為偶數，N - 2為奇數，顯然，數學知識告訴我們，相鄰的兩個正整數互質。同樣的，相鄰的兩個奇數也是互質的，那麼此時題目要求的答案為N * (N - 1) * (N - 2)。
-
N為偶數時
因為當N >3時，N 和當N - 3是可能不是互質的，例如3和6。是以偶數時又分為兩種可能性：
2.1 當3不能整除N時
當N為偶數時，N - 2同樣為偶數，那麼就不能滿足上面思路的第1點了。但是N和N - 1還是互質的，是以
在貪心政策下，我們優先考慮使用更小的值去替換N - 2，而不是替換N 和 N - 1。
經計算發現 N - 3滿足要求，是以此時答案為N * (N - 1) * (N - 3)。
2.2 當3能整除N時
因為N能夠被3整除，是以N - 3同樣能被3整除，為了不違反第1點，我們再次優先用更小的值替代 N -3（為什麼又是換掉第三個？因為我貪心啊）。
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
if (n <= 2){
cout << n;
return 0;
}
if (n%2 != 0) cout << n*(n-1)*(n-2);
else if (n%3 != 0){
cout << n*(n-1)*(n-3);
}
else cout << (n-1)*(n-2)*(n-3);
return 0;
}