[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;
}