C. LCM Challenge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.
But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than n.
Can you help me to find the maximum possible least common multiple of these three integers?
Input
The first line contains an integer n (1 ≤ n ≤ 106)
— the n mentioned in the statement.
Output
Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than n.
Sample test(s)
input
9
output
504
input
7
output
210
Note
The least common multiple of some positive integers is the least positive integer which is multiple for each of them.
The result may become very large, 32-bit integer won't be enough. So using 64-bit integers is recommended.
For the last example, we can chose numbers 7, 6, 5 and
the LCM of them is 7·6·5 = 210. It is the maximum value we can get.
题目大意：
就是给你一个数 n，让你求 <= n的三个不重复的数的最小公倍数最大。。。可以参考样例
解体思路：
当 n==1 , 2 3 的时候需要特判一下。。
然后就当 n 是奇数的时候，就是等于 n*(n-1)*(n-2);
当 n 是偶数的时候， n 与 n-2 有最大公约数 2，还得考虑 n 与 n-3是不是有最大公约数。。。
如果n 与 n-3有最大公约数，那么就需要比较(n-1)*(n-2)*(n-3), 和n*(n-1)*(n-2)/2
否则的话，就需要比较(n-1)*(n-2)*(n-3) , n*(n-1)*(n-3)) 和 n*(n-1)*(n-2)/2
上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+5;
const int mod = 1073741824;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
if(b == 0)
return a;
return gcd(b, a%b);
}
int main()
{
LL n;
while(cin>>n)
{
if(n==1 || n==2)
cout<<n<<endl;
else if(n == 3)
puts("6");
else
{
if(n & 1)
cout<<n*(n-1)*(n-2)<<endl;
else
{
if(gcd(n,n-3) == 1)
cout<<max(max((n-1)*(n-2)*(n-3),n*(n-1)*(n-3)),n*(n-1)*(n-2)/2)<<endl;
else
cout<<max((n-1)*(n-2)*(n-3),n*(n-1)*(n-2)/2)<<endl;
}
}
}
return 0;
}
/**
6 -> 60
508 -> 130065780
**/