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.
Definition
- Class:
- MaximizingLCM
- Method:
- maximize
- Parameters:
- int, long
- Returns:
- long
- Method signature:
- long maximize(int N, long M)
- (be sure your method is public)
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
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
37
2
Returns: 2
37
3
Returns: 6
29
4
Returns: 12
25
5
Returns: 60
23
6
Returns: 60
21
7
Returns: 420
21
5
Returns: 60
19
8
Returns: 840
18
9
Returns: 2520
18
10
Returns: 2520
17
11
Returns: 27720
16
13
Returns: 360360
15
15
Returns: 360360
14
15
Returns: 360360
14
16
Returns: 720720
14
17
Returns: 12252240
14
18
Returns: 12252240
14
19
Returns: 232792560
3
47
Returns: 97290
1
1
Returns: 1
1
123456789012345678
Returns: 123456789012345678
2
1000000000
Returns: 999999999000000000
2
999999987
Returns: 999999973000000182
3
1000000
Returns: 999996000003000000
3
999996
Returns: 999982000106999790
3
999984
Returns: 999946000970994186
3
999972
Returns: 999910002698973030
4
31620
Returns: 999301112903423610
4
31614
Returns: 998542780009617444
4
31542
Returns: 989476409883091020
4
31610
Returns: 998037454591610290
4
3170
Returns: 100630297516330
4
31580
Returns: 994253699545053220
5
3880
Returns: 874367128099410750
5
3670
Returns: 661796303688381540
5
3980
Returns: 993645806238611400
5
3972
Returns: 983689513295448960
5
3963
Returns: 973320122339250882
5
3960
Returns: 969394706926180710
6
1000
Returns: 969358035302363970
6
996
Returns: 946198330765082430
6
984
Returns: 881300687246815374
6
978
Returns: 849390777769825200
6
946
Returns: 690525253466925030
6
976
Returns: 835480591030503600
7
372
Returns: 874598390200135440
7
370
Returns: 832165045123039920
7
366
Returns: 770021153486124540
7
220
Returns: 19547022822260010
7
219
Returns: 19547022822260010
7
66
Returns: 2349575766720
7
276
Returns: 101357606500099950
7
218
Returns: 19011487950417270
8
177
Returns: 681177851706752400
8
174
Returns: 591680108386205748
8
168
Returns: 425053368064140690
8
22
Returns: 232792560
8
96
Returns: 3219540185335110
8
136
Returns: 66348193572969000
8
95
Returns: 3219540185335110
8
135
Returns: 65372484843954750
9
100
Returns: 332443488169602810
9
98
Returns: 312295397977505670
9
75
Returns: 21984059707707630
9
99
Returns: 332443488169602810
9
96
Returns: 228587353158792810
9
97
Returns: 312295397977505670
9
95
Returns: 228587353158792810
10
63
Returns: 150533514491839710
10
62
Returns: 150533514491839710
10
61
Returns: 140821674847204890
10
58
Returns: 44879816907403170
10
57
Returns: 40237077227326980
10
56
Returns: 36001595413924140
11
43
Returns: 19029471027883680
11
42
Returns: 4868004216435360
11
41
Returns: 4868004216435360
2
24174
Returns: 584358102
2
128654
Returns: 16551723062
2
1945526
Returns: 3785069471150
2
4718803
Returns: 22267097034006
2
255999072
Returns: 65535524608862112
3
6
Returns: 60
3
24
Returns: 10626
3
78
Returns: 438900
3
133
Returns: 2299836
3
579
Returns: 193099974
3
999
Returns: 994010994
3
1105
Returns: 1345571760
3
1193
Returns: 1693668696
3
2930
Returns: 25119426190
3
3792
Returns: 54439935210
3
5926
Returns: 207965710650
3
13649
Returns: 2542184340144
3
52820
Returns: 147354126116860
3
85092
Returns: 616077816143910
3
94494
Returns: 843694317048996
4
6
Returns: 60
4
62
Returns: 12718866
4
133
Returns: 292183710
4
206
Returns: 1723110690
4
221
Returns: 2310568260
4
306
Returns: 8456342160
4
348
Returns: 14207536770
4
432
Returns: 33949305390
4
764
Returns: 336700940268
4
858
Returns: 535019649480
4
1394
Returns: 3751830986358
4
3186
Returns: 102679277347920
4
7526
Returns: 3204330980811450
4
10112
Returns: 10446279306604416
4
16348
Returns: 71387043712909260
5
5
Returns: 60
5
6
Returns: 60
5
8
Returns: 840
5
12
Returns: 27720
5
13
Returns: 90090
5
19
Returns: 1007760
5
49
Returns: 204990030
5
51
Returns: 252523950
5
103
Returns: 9990000900
5
157
Returns: 86580571770
5
203
Returns: 323119201818
5
242
Returns: 776330265810
5
1357
Returns: 4550833567542570
5
1832
Returns: 20456387190628200
6
7
Returns: 420
6
8
Returns: 840
6
20
Returns: 11085360
6
29
Returns: 239519700
6
58
Returns: 22193987970
6
70
Returns: 73540742340
6
75
Returns: 117565211550
6
102
Returns: 803651926770
6
171
Returns: 21530875414230
6
189
Returns: 39825807866460
6
200
Returns: 55233258023580
6
211
Returns: 79015505128560
6
282
Returns: 449921837687850
6
643
Returns: 67967875771966170
6
805
Returns: 264437724101810490
7
14
Returns: 360360
7
40
Returns: 39683091630
7
41
Returns: 70739424210
7
54
Returns: 570683925084
7
120
Returns: 249001171236090
8
8
Returns: 840
8
12
Returns: 27720
8
31
Returns: 126226881900
8
106
Returns: 8147538041012370
8
131
Returns: 55872163008816000
9
11
Returns: 27720
9
15
Returns: 360360
9
17
Returns: 12252240
9
25
Returns: 26771144400
9
32
Returns: 1875370816800
10
17
Returns: 12252240
10
24
Returns: 5354228880
10
28
Returns: 80313433200
10
45
Returns: 1539148391961180
10
52
Returns: 8954084622674100
11
11
Returns: 27720
11
12
Returns: 27720
11
24
Returns: 5354228880
11
40
Returns: 1068586291412640
11
43
Returns: 19029471027883680
12
14
Returns: 360360
12
15
Returns: 360360
12
22
Returns: 232792560
12
31
Returns: 72201776446800
13
13
Returns: 360360
13
18
Returns: 12252240
13
20
Returns: 232792560
13
22
Returns: 232792560
13
24
Returns: 5354228880
1
2
Returns: 2
2
1
Returns: 1
2
2
Returns: 2
4
10000
Returns: 9989004099390030
3
12
Returns: 990
5
345
Returns: 4677953899080
6
493
Returns: 13643562740250120