MaximizingLCM
SRM 815 · 2021-10-06 · by misof
SRM 815 · 2021-10-06 · by misof · Brute Force, Math, Simple Search, Iteration
Problem Statement
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.
Examples
0)
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.
1)
10 10 Returns: 2520
Here, the answer is clearly equal to lcm(1,2,3,4,5,6,7,8,9,10).
2)
50 1 Returns: 1
3)
50 2 Returns: 2
4)
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.
Coding Area
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