LCM Challenge
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.
--------------------------------------------------editorial-------------------------------------------------------
It's a simple problem, but many competitors use some wrong guess and fail.
First of all we should check if n<=3 and then we should output 1,2,6. and if n is odd, the answer is obviously(3 consicutive no have always lcm there product if start with odd number ) n(n-1)(n-2).
if n is even, of course we can use (n-1)(n-2)(n-3), so these three number wouldn't be very small compared to n. so just iterate every 3 number triple in [n-50,n] and update the answer.
--------------------------------------------------------code---------------------------------------------------------
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64 lld;
lld gcd(lld a, lld b) {
return !b ? a : gcd(b, a%b);
}
lld gao(lld n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
if (n == 3)
return 6;
if (n&1)
return n*(n-1)*(n-2);
lld a = (n-1)*(n-2)*(n-3);
lld b = n*(n-1);
for (lld t=n-2; b*t > a; t--) {
lld g = gcd(b, t);
// printf("t=%I64d g=%I64d\n",t,g);
if (b/g*t > a)
a = b/g*t;
}
return a;
}
int main() {
lld n;
scanf("%I64d",&n);
printf("%I64d\n",gao(n));
return 0;
}
------------------------------------------------------------------------ANOTHER APPROACH 0=---------------------------
we can also solne this problem in another way , we can observe that answewr will be from atmost all last 50 triplet and calculate answer
----------------------------------code----------------------------------------------------------------------------
#include <stdio.h>
#include <ctype.h>
#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <utility>
#include <assert.h>
#define MPI 3.141592653589793238462643
#define eps 1e-8
#define inf ((int)1e9)
#define pb push_back
#define mp make_pair
using namespace std;
long long res;
long long lcm (long long a, long long b)
{
return (a*b)/__gcd(a,b);
}
int main()
{
int i, j, k, t, n;
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
scanf("%d", &n);
t=min(50,n);
for (i=0; i<t; i++)
for (j=i; j<t; j++)
for (k=j; k<t; k++)
res=max(res,lcm(n-i,lcm(n-j,n-k)));
cout<<res<<endl;
return 0;
}
