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