MINLCM1 - Editorial

PROBLEM LINK:

Contest

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

LCM(X,2\cdot X)=2\cdot X
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

LCM(X\cdot K-1, X\cdot K)=(X\cdot K-1)\times(X\cdot K)
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:

O(1)

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

A more interesting problem would be if N <= i < j <= M, where for example the minimum for N = 21, M = 25 would be 168 at i = 21, j = 24