问题描述
已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数,表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。
solution
最小公倍数最大,则三个数据的最大公约数最小,数据本身最大。
最小的最大公约数1,即三个数两两互质。
分析对于不同的n有
- n小于3时==>最大的最小公倍数ans = n
- 当n是奇数时, n, n-1, n-2互质且数值最大==》ans = n*(n-1)*(n-2)
- 当n是偶数时,n和n-2显然不满足互质,考虑换掉n或n-2。
- 当n%3 == 0时,显然n又和n-3有公约数3 , 抛弃n选择顺延一位符合奇数的情况==》ans = (n-1)(n-2)(n-3)
- 当n%3 != 0时,==>则ans = n(n-1)(n-3)
#include<stdio.h>
typedef long long ll;
int main(){
ll n;
scanf("%lld", &n);
if(n < 3) printf("%lld", n);
else if(n % 2 == 1) printf("%lld", n * (n - 1) * (n - 2));
else {
if(n % 3 == 0) printf("%lld", (n - 1) * (n - 2) * (n - 3));
else printf("%lld", n * (n - 1) * (n - 3));
}
return 0;
}