MissingLCM
SRM 661 · 2015-05-01 · by lg5293
Problem Statement
The least common multiple (denoted "lcm") of a non-empty sequence of positive integers is the smallest positive integer that is divisible by each of them. For example, lcm(2)=2, lcm(4,6)=12, and lcm(1,2,3,4,5)=60.
Alice had a positive integer N. Then she chose some positive integer M that was strictly greater than N. Afterwards, she computed two values: the value A = lcm(N+1, N+2, ..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.
You are given the
Constraints
- N will be between 1 and 1,000,000, inclusive.
1 Returns: 2
Alice needs to choose an M > 1 such that lcm(2,...,M) = lcm(1,...,M). We can see M=2 is the minimum value that works, since lcm(1,2) = lcm(2) = 2.
2 Returns: 4
3 Returns: 6
We have lcm(4,5,6) = lcm(1,2,3,4,5,6) = 60.
4 Returns: 8
5 Returns: 10
42 Returns: 82
Oh... that doesn't fit the pattern.
Submissions are judged against all 57 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MissingLCM with a public method int getMin(int N) · 57 test cases · 2 s / 256 MB per case