已知一個(gè)正整數(shù)N，問從1~N中任選出三個(gè)數(shù)，他們的最小公倍數(shù)最大可以為多少。
輸入格式輸入一個(gè)正整數(shù)N。
輸出格式輸出一個(gè)整數(shù)，表示你找到的最小公倍數(shù)。樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1 <= N <= 106。
分析
1---N中我們應(yīng)該從大到小考慮，首先我們最能想到的就是 N為奇數(shù)的時(shí)候 n,n-1,n-2,（n-1）為偶數(shù)所以此時(shí)最大的最小公倍數(shù)為三個(gè)數(shù)的乘積（由于任意連續(xù)的奇數(shù)互質(zhì)）所以此時(shí)的最大的最小公倍數(shù)為三個(gè)數(shù)的連乘積的形式如果n等于偶數(shù)那么n與n-2必定有質(zhì)因數(shù)2，所以此時(shí)n ,n-1,n-3由于n為偶數(shù)，所以n-1，n-3必定為奇數(shù)，此時(shí)還會(huì)出現(xiàn)一種可能性就是n與n-3有質(zhì)因數(shù)3所以我們必須判斷是否n能被3整數(shù)，如果能我們將n轉(zhuǎn)換為n-2即可此時(shí)我們解決了函數(shù)問題，由于函數(shù)的規(guī)模，所以我們決定選用long long 的數(shù)據(jù)類型#include<iostream>using namespace std;//最小公倍數(shù) 最小公倍數(shù)=兩整數(shù)的乘積÷最大公約數(shù)long long MinCom(long long n)//1-n中三個(gè)數(shù)最大的最小公倍數(shù){ long long max; if (n % 2 == 1)max=n*(n-1)*(n-2); else { if (n % 3 == 0) max = (n - 1)*(n - 2)*(n - 3); else max = n*(n - 1)*(n - 3); } return max;}int main(){ int n; cin >> n; cout << MinCom(n); return 0;}
新聞熱點(diǎn)
疑難解答
