# PROBLEM LINK:

# DIFFICULTY:

SIMPLE

# PROBLEM:

Given positive integers X and K. Determine the minimum and maximum possible values of LCM(i, j), where X\le i < j \le X\cdot K.

# EXPLANATION:

A bit of trial and error shows that the least possible LCM is equal to

## Proof of optimality

We prove by contradiction.

Assume there exists some i<j such that LCM(i,j)< 2\cdot X. Since LCM(i,j) is always \ge i,j - it follows that X\le i<j < 2\cdot X.

Now, i can’t be a divisor of j, since the greatest proper divisor of j is at most \frac{j}{2}, which is lesser than X. This implies LCM(i,j)=j\cdot p where p>1.

2\cdot X < j\cdot 2\le j\cdot p=LCM(i,j)\implies 2\cdot X<LCM(i,j)

Thus, a contradiction to our initial proposition and we are done.

Since the LCM of two consecutive integers equals their product, a bit of experimental deduction shows that the maximum possible LCM is equal to

## Proof of optimality

We know that LCM(i,j) is always \le i\cdot j. This implies that the greatest possible LCM is \le (X\cdot K-1)\times(X\cdot K).

This is equal to our LCM above, and thus we have shown that no greater value is possible.

Don’t forget to handle a possible overflow when computing this value!

# TIME COMPLEXITY:

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters