MaximizingLCM
SRM 815 · 2021-10-06 · by misof
Problem Statement
Suppose we have to select exactly N positive integers, each between 1 and M, inclusive. (The integers do not have to be distinct.)
Determine and return the largest possible value of the least common multiple of these integers.
Notes
- The last constraint implies that the answer for any valid test case won't exceed 10^18.
Constraints
- N will be between 1 and 50, inclusive.
- M will be positive.
- M to the power of N will not exceed 10^18.
Statement by TopCoder, Inc. — view the original on the archive.
6 3 Returns: 6
One optimal solution is to select the numbers 1, 1, 1, 2, 2, 3. Their least common multiple is 6, which is clearly the best possible answer.
10 10 Returns: 2520
Here, the answer is clearly equal to lcm(1,2,3,4,5,6,7,8,9,10).
50 1 Returns: 1
50 2 Returns: 2
37 1 Returns: 1
Submissions are judged against all 187 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaximizingLCM with a public method long long maximize(int N, long long M) · 187 test cases · 2 s / 256 MB per case