Problem Statement
Mahdi is playing a game in Quera.
In the beginning he is standing on position 0. His goal is to reach position n-1.
From any position x other than n-1, he can simply go to position x+1. Each such move costs a.
From any position x he can jump to position (A*x+B) mod n. Each such jump costs b.
Compute and return the minimal total cost of reaching the goal.
Definition
- Class:
- MahdiJumping
- Method:
- minDis
- Parameters:
- int, int, int, int, int
- Returns:
- long
- Method signature:
- long minDis(int n, int A, int B, int a, int b)
- (be sure your method is public)
Constraints
- n, A, a, and b will each be between 1 and 5,000,000, inclusive.
- B will be between 0 and 5,000,000, inclusive.
Examples
7
1
1
1
5
Returns: 6
Mahdi will simply go to 1, 2, 3, 4, 5, 6.
5
2
2
1
2
Returns: 3
Mahdi will go to x = 1 and then to x = 4.
5
5
5
5
5
Returns: 20
5000000
314
5
1
2
Returns: 31
5000000
5
5
5
5
Returns: 175
5000000
1
0
1
1
Returns: 4999999
5000000
2
0
1
10
Returns: 209
1
4
7
4
7
Returns: 0
36865
15624
442221
453
4431
Returns: 22452
137274
8
502
133466
1899
Returns: 508641
3021
112601
24315
3
3448
Returns: 3847
2919165
137
26
13
463249
Returns: 741267
1578808
11
1471
39986
13976
Returns: 477508
12107
199646
2212
53228
469488
Returns: 2632708
5905
643758
1482867
8072
332
Returns: 25440
270108
37
6
127993
14181
Returns: 881042
48
2038033
1709164
1
108
Returns: 47
179310
62
80
10
442527
Returns: 471917
1871415
12
16398
1305216
9292
Returns: 7826960
34126
277
21
129890
127
Returns: 161894
1999825
267380
5
26
1146483
Returns: 1212341
2298
5104
1
567
211724
Returns: 229301
2667
202679
608911
519702
1130
Returns: 581852
233
13987
1012
670723
4
Returns: 670815
500048
1
296847
1013
80495
Returns: 4406331
3490
1365
17124
313621
4024309
Returns: 17404484
407260
1098454
180692
3301146
3
Returns: 26409288
4121671
4656
15
225958
425563
Returns: 7392689
184777
1240351
12
6821
225475
Returns: 853771
151
971114
2253
2279
6290
Returns: 27986
5821
726
26198
30816
1136
Returns: 91168
501
1
15686
122929
794529
Returns: 6686102
9871
638
59
2042
12034
Returns: 60606
1600339
1071
922034
1008547
712507
Returns: 12759885
71145
43
606006
59704
2
Returns: 119444
354371
941509
1
7
1
Returns: 51
1001519
1831233
14
9
14941
Returns: 28450
2534462
707611
4188288
61554
622565
Returns: 4268301
108448
11413
1837
5
54595
Returns: 58325
192
38843
2169
4762
759419
Returns: 826087
1490618
99310
628
147442
693
Returns: 525486
777321
7979
1
770967
1833120
Returns: 21603663
214
5
317660
174
5
Returns: 229
1401211
36
5
468600
2546
Returns: 1306370
208371
188624
3552225
6
8
Returns: 88
1301
1210
1902
111693
121307
Returns: 1276693
490754
3829876
34254
105
3
Returns: 441
240
327172
13
9158
1407
Returns: 50011
253966
127793
81201
178
1103899
Returns: 1300767
4167355
1314
2784262
586
3
Returns: 1857
32
432
91
3566
22
Returns: 14286
280252
818
10007
15045
4086
Returns: 165117
4467
519461
197
4575
1
Returns: 9167
1878
2411
3436
18604
7
Returns: 18744
4623
45
236
45708
518
Returns: 55032
131
365
228765
46809
1844
Returns: 67093
58
1729
1
1
2
Returns: 8
1055623
2
7897
75
458
Returns: 8761
1778098
2
830
3
29712
Returns: 247203
19330
471
2450
7188
50
Returns: 64942
16
362486
23
4
15198
Returns: 60
241968
329032
28
251679
331
Returns: 1065634
69
388745
329392
4
19
Returns: 42
1315507
830593
481462
259016
548887
Returns: 6235063
661
158
25
1032143
2076289
Returns: 9301290
424261
15560
716682
1
64856
Returns: 65000
221113
3284
915
4387
806065
Returns: 1841397
495
4926
2548645
279942
3441
Returns: 2526360
5000000
1
2703
565995
16071
Returns: 403038819
21217
387
1861
2564972
86
Returns: 2590686
3203
3127678
27555
27
10
Returns: 198
744
215061
1480476
1571129
3
Returns: 4713405
88072
43927
115
2322254
54184
Returns: 241568600
2410252
304
22
455
12
Returns: 2588
3597470
14
2969
768
860689
Returns: 3423027
4515823
741823
968
1257
21
Returns: 5052
6906
304
724
3
751890
Returns: 20715
2032
37843
4286
1362944
14
Returns: 1363322
11801
11301
5
1517308
154475
Returns: 7950374
3855749
834
2534
6
23326
Returns: 48728
150
220374
516031
143
1655
Returns: 3800
100247
293268
6
23601
129150
Returns: 928962
13410
12268
868849
372102
355188
Returns: 2875332
1514
2
797481
833300
107
Returns: 54249
5000000
88318
1787
42
4166753
Returns: 4245587
68
7898
26026
622794
2081040
Returns: 7063392
6830
734
9428
451
1965
Returns: 12370
10831
174
2991
549
124
Returns: 3631
27
1
468
96477
31268
Returns: 834352
37
28
22517
139
7800
Returns: 5004
2515391
138017
248604
258340
346684
Returns: 5615212
756
419
127
101546
24752
Returns: 200554
20202
193
136
23
19161
Returns: 25808
23463
1216
336
440
21
Returns: 1489
87
2
631948
554
1403
Returns: 6943
121
306
712
521632
675278
Returns: 4848334
380
194110
851949
488
1
Returns: 2
1076
11047
505
121
1
Returns: 161
3692
89006
43
576911
104
Returns: 1731669
104842
303
747
3
753
Returns: 1731
15670
43
210439
25859
565
Returns: 65843
8813
2384784
943391
484959
28
Returns: 71484
94921
119742
22360
461
1710
Returns: 15272
224
10494
7
188
1
Returns: 1130
2203618
1836
210469
96
4
Returns: 324
2763
893999
2390
4190875
399
Returns: 4213219
46161
3
48023
2555841
105599
Returns: 8913246
918
359
102270
42
1337
Returns: 2639
4946117
7
249999
442221
453
Returns: 950580
4951434
567183
8579
8
502
Returns: 2368
4994877
133466
1899
188
112601
Returns: 261298
4957962
136
229157
3448
182447
Returns: 874901
4931276
2
1224
3619
98675
Returns: 1767950
4912726
1524540
1471
39986
13976
Returns: 395594
4988454
756
199646
2212
53228
Returns: 303604
4973759
6227
94494
643758
1482867
Returns: 22806822
4949789
49357
680737
16881
37
Returns: 43863
4909778
499
14181
3
2038033
Returns: 2068681
4992823
1709164
1
108
11206
Returns: 42474
4923157
45788
19
27
116963
Returns: 173366
4914166
483
1
9292
2132
Returns: 104788
4934635
2
63
127
124989
Returns: 1645410
4973872
267380
5
26
1146483
Returns: 1227265
4981533
143
5104
1
567
Returns: 1464
4971808
756
682837
202679
608911
Returns: 7912347
4973788
55228
144751
14
13987
Returns: 31474
4939690
518654
670723
4
31253
Returns: 33881
4902343
9276
1013
80495
218
Returns: 260398
4943399
61
1
4024309
25453
Returns: 12884688
4983628
137306
180692
3301146
3
Returns: 26409297
4971074
57914
4
128099
225958
Returns: 4113446
4975820
933
2956438
1240351
12
Returns: 1254139
4953094
1761
9
971114
2253
Returns: 2805127
5000000
1234567
1234567
1234567
192811
Returns: 12112567
5000000
4343243
2343435
4477777
4777777
Returns: 88377763
5000000
5000000
5000000
5000000
5000000
Returns: 24999995000000
4999888
4999887
4999886
4999885
4999
Returns: 5004884
5000000
1
5
1
5000000
Returns: 4999999
5000000
4399978
444
600000
300000
Returns: 10800000
4491416
520323
2814059
4230437
2337229
Returns: 55766599
5000000
139
29
40000
1110000
Returns: 6670000
4987987
4989987
2
4987989
1987987
Returns: 70663646
4999999
3389348
383347
4383499
999679
Returns: 47294253
3052872
2403684
978913
235809
4893111
Returns: 34428411
5
1
3
10000
1
Returns: 3
3668033
4039245
279685
921170
972533
Returns: 21036185
5000000
1
2500000
1
2500000
Returns: 4999999
2810602
1320191
4335997
4976241
1524438
Returns: 62273571
4
2
0
2
1
Returns: 5
1000000
1000000
1000001
5000000
1
Returns: 4999990000001
5
1
2
1
10
Returns: 4
5000000
4000001
4987654
4000001
4987654
Returns: 503999999
5000000
1
0
5000000
5000000
Returns: 24999995000000