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