已知一個正整數N，問從1~N中任選出三個數，他們的最小公倍數最大可以為多少。
輸入格式輸入一個正整數N。
輸出格式輸出一個整數，表示你找到的最小公倍數。樣例輸入9樣例輸出504數據規模與約定1 <= N <= 106。
思路:這個題其實還真應該好好想想,剛開始就很想當然的認為找了三個最大的數相乘,沒考慮要分奇偶情況討論靜下心來一想其實還真是這么回事:對于奇數的話我們挑選出最大的三個數：奇偶奇 n n-1 n-2 兩個奇數，雖然變化了2但是都是奇數,沒有公因子2，所以此時他們是最大的最小公倍數.對于偶數如果我們還是挑選出三個最大的數的話：偶奇偶 n n-1 n-2 兩個偶數肯定會有一個公因子2,此時就不會滿足最大,為了還是能滿足兩個奇數一個偶數 我們選擇 n n-1 n-3 即減少一個,但是新的問題又來了 n和 n-3 可能會包含一個新的公因子3 （因為他們之間變化了3，或者相差3 不會再出現更大的公因子了）如果包含了的話會使這個最大最小公倍數更小,所以需要特判一下,如果n和n-3有公因子3 那么我們就只能將n減少 選擇 n-1 n-2 n-3 三個連續的最大數 奇偶奇 就滿足了n為奇數的情況的最大;#include<bits/stdc++.h>using namespace std;long long n;int main(){ scanf("%lld",&n); if(n<=2) { PRintf("%lld/n",n); } else if(n%2==1) printf("%lld/n",n*(n-1)*(n-2)); else { if(n%3) printf("%lld/n",n*(n-1)*(n-3)); else printf("%lld/n",(n-1)*(n-2)*(n-3)); } return 0;}
新聞熱點
疑難解答
