## 算法訓練 最大最小公倍數 ? 時間限制：1.0s ? 內存限制：256.0MB ? 問題描述 已知一個正整數N，問從1~N中任選出三個數，他們的最小公倍數最大可以為多少。 輸入格式 輸入一個正整數N。 輸出格式 輸出一個整數，表示你找到的最小公倍數。 樣例輸入 9 樣例輸出 504 數據規模與約定 1 <= N <= 106。 這道題，首先說明一下，公認的5,8,9,10四個測試數據有錯誤，詳情看論壇。。。 還有，類型用long long， 題意很簡單，就是求三個互質的數，何為互質？兩兩最大公約數為1， 而且，在所有兩兩互質的數中，肯定值越大乘積越大，因此，可以向這方面做。 但是，列出幾個例子就會發現，這題目是有規律的： 例1： 1 2 3 4 5 6 （n為6） 例2： 1 2 3 4 5 6 7（n為7） 例3： 1 2 3 4 5 6 7 8 （n為8） 規律： ①. 當n為奇數時， n*n-1*n-2最大 ②. 當n為偶數時，有兩個選擇方案，要么選n-1*n-2*n-3 要么選n*n-1*n-3，這兩個選擇差就差在與3的余數關系， 這個優先策略很簡單，盡量先選最大的，然后往下選，但是，如果你選了最大的以后，比如例1中，選了6，就 無法選擇4也無法選擇3，甚至2，所以，這種情況就不能去選擇6，只能退一步選擇n-1，再討論 這樣代碼就出來了： ~~~ #include<iostream> using namespace std; int main() { long long n, number; cin>>n; if( n <= 2) { cout<<2; } else if(n % 2) { number = n * (n - 1) * (n - 2); cout<<number; } else { if( n % 3 == 0) { number = (n - 1) * (n - 2) * (n - 3) ; } else number = n * (n - 1) * (n - 3); cout<<number; } return 0; } ~~~