# LCM Challenge - 235 A

https://codeforces.com/problemset/problem/235/A

## Simplified Problem Statement

Given `n`

, take 3 numbers `a, b, c <= n`

. Maximize `LCM(a, b, c)`

.

## Constraint

`n <= 10^6`

.

## Analysis

We want to minimize common divisor among the number, for `LCM(a, b, c) = a*b*c / GCD(a, b, c)`

. Is it possible to have `GCD(a, b, c)`

to become 1? If we have `2k-1`

, `2k`

, `2k+1`

, it is clear that the GCD will be 1. However, the number `n`

might be even, hence `2k+1`

, which is the max value is not equal to `n`

.

Looking at the test cases. For `n`

= 9 and 7, the solution seems to be consistent with our method. Which are 504 and 210 respectively.

Let’s see for even valued `n`

. The number `2k-2`

, `2k-1`

, `2k`

should have `GCD`

of 2. Thus for big enough `n`

, `2k-1`

, `2k`

, `2k+1`

seems to be the best solution.

We need to consider the fact that the three numbers `a`

, `b`

, and `c`

does not need to be different.

Uh oh! The formula `LCM(a, b, c) = a*b*c / GCD(a, b, c)`

is completely wrong. As an example, `LCM(7, 7, 6)`

is not 294 but rather 42. For sure, because it seems to be easy for a `C`

problem if that’s so. Moving on, we can actually use `lcm(a,b,c) = lcm(a, lcm(b,c))`

, which by analyzing GCD will generate us
`lcm(a,b,c) = a*lcm(b, c)/GCD(a, lcm(b,c)) = a*b*c/GCD(b,c)*GCD(a, b*c/GCD(b,c))`

. Bleh.. expanding the equation doesn’t seem to be very helpful.

So what now? If we go back to the initial hypothesis that `2k-1`

, `2k`

, `2k+1`

will give us the best result, maybe we can try to prove directly from there?

We can try from smaller n

- n = 1 -> 1,1,1 = 1
- n = 2 -> 2,2,2 = 2
- n = 3 -> 1,2,3 = 6
- n = 4 -> 2, 3, 4 = 12 (better than 1, 2, 3 = 6)
- n = 5 -> 3, 4, 5 = 60
- n = 6 -> 4, 5, 6 = 60 (equally good as 3, 4, 5 = 60) (I believe that as
`n`

grows, the solution with more “odds” will perform better and this is the tipping point) - n = 7 -> 5, 6, 7 = 210
- n = 8 -> 6, 7, 8 = 168 (now it’s less than 5, 6, 7 = 210).

I think we can try to submit this. As i’m pretty confident.

## Implementation

The special cases that doesn’t follow the patterns are n = 1, 2, 3, 4. So we can hardcode this.

```
int main() {
setIO();
ll n; re(n);
if(n == 1) ps(1);
else if(n == 2) ps(2);
else if(n == 3) ps(6);
else if(n == 4) ps(12);
else if(n & 1) ps((n-2)*(n-1)*n); // n is odd
else ps((n-3)*(n-2)*(n-1));
}
```

Uh oh! This result on WA on test 33. This might be resulted because of not enough bit space I guess? I don’t think it’s a fundamental error on the solution but rather an edge case. Before looking at the test result and peeking at the issue, let us try to test some first. Strangely for n = `1000000`

it still work and produce `999994000010999994`

. So there might be an edge case? Does anything happen that might cause `2k-3`

, `2k-1`

, `2k`

be a better solution (for even `n`

). Let us see, for `n=8`

, this pattern will generate 5, 7, 8 = 280, which is actually bigger than 210! Oh lol. But I need to be carefull since if `n`

is divisible by `3`

, like in the case of `6`

, we will have duplicate factor of `3`

. I think we can simply try to get the max of both. Uh oh! Max wouldn’t work. Since we need to take into account the factor of 3 thing. I guess we can try if `n`

is divisible by 3, we use the old pattern, otherwise use the new pattern.

```
int main() {
setIO();
ll n; re(n);
if(n == 1) ps(1);
else if(n == 2) ps(2);
else if(n == 3) ps(6);
else if(n == 4) ps(12);
else if(n & 1) ps((n-2)*(n-1)*n); // n is odd
else if(n % 3 == 0) ps((n-3)*(n-2)*(n-1)); // n is divisible by 3
else ps(n*(n-1)*(n-3));
}
```

Accepted!