[IOICamp] 最小公倍數問題

題目連結:https://judge.ioicamp.org/problems/57
因為不知道是不是大家都看的到題敘,所以稍微敘述一下好了:
總共有T測資,給定一個N,請你選出三個數$1 \leq i,j,k \leq n$使得其最小公倍數最大($N \leq 10^6$)
然後我一開始不知道該怎麼做,只知道明顯要拿最大且互質的三組數,直到虞樸學長很電的跟我們說其實答案只會在$n,n-1,n-2,n-3$,想了很久並跟別人討論後才發現,考慮$n \geq 4$的情況下(前面三種特判就好),因為顯然兩個相鄰的數必定互質(由輾轉相除可知),所以只要考慮弟三個數要跟這兩個數互質。那假如現在已有$n,n-1$兩個數,若$2|n$那$2|n-2$也必定發生,所以這時我們就只能考慮$n-3$,若$gcd(n,n-3) \neq 1$那應該可以確定$3|n$,而我們也知道$2|n-2$,表示若取了n就不能取n-2及n-3,那不妨改成取$n-1,n-2,n-3$試試看,因為已經有前面的條件,所以應該可以證明出取他們必定互質,所以就知道了完整的規則了。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		lld n,ans;
		scanf("%lld",&n);
		if(n==1){
			ans=1;
		}else if(n==2){
			ans = 2;
		}else if(n==3){
			ans = 6;
		}else if(n%6==0){
			ans=(n-1)*(n-2)*(n-3);
		}else if(n%2==0){
			ans=n*(n-1)*(n-3);
		}else{
			ans=n*(n-1)*(n-2);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology