January 21, 2021

# 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!