Problem Statement
For a positive integer x, we say that the base b >= 2 is light if the integer x written in base b has digit sum at most 2.
For example:
- Base b=10 is light for x=1000, x=10010 and also for x=200.
- Base b=2 is light for x=65 because 65 written in base-2 is "1000001", and the digit sum of that is 2.
- Base b=47 is light for x = 4418 = 2*47*47.
For each of the numbers A, A+S, A+2*S, ..., A+(N-1)*S, determine their smallest light base. Return the sum of those bases, modulo (10^9 + 7).
Definition
- Class:
- Based
- Method:
- solve
- Parameters:
- long, long, int
- Returns:
- int
- Method signature:
- int solve(long A, long S, int N)
- (be sure your method is public)
Notes
- Each positive integer has at least one light base, so the return value is always well-defined.
Constraints
- N will be between 1 and 100,000, inclusive.
- A will be positive.
- S will be positive.
- All N numbers of the form A + i*S will be between 1 and 10^18, inclusive.
Examples
30
2
5
Returns: 28
We are interested in the numbers 30, 32, 34, 36, and 38. For the numbers 32, 34, and 36 the smallest light base is b=2. (They are "100000", "100010", and "100100" in base-2.) The smallest light base for x=30 is b=3 ("1010"), and the smallest light base for x=38 is b=19 ("20"). The return value is (3+2+2+2+19) mod (10^9 + 7).
1
4417
2
Returns: 49
The smallest valid base is b=2. This is a light base for x=1, as 1 in base 2 is "1". As mentioned in the statement, b=47 is a light base for x=4418. It turns out to be the smallest light base for this x.
987654321987654321
12347
100000
Returns: 190937008
987654321987654321
12347
2
Returns: 611117350
The return value is (987654321987654320 + 493827160993833334) mod (10^9 + 7).
1099511627776
1099511627776
99945
Returns: 124571092
4398046511104
5497558138880
99970
Returns: 369263603
847288609443
847288609443
99958
Returns: 785667945
10167463313316
3389154437772
99965
Returns: 324642722
1099511627776
1099511627776
99949
Returns: 420346487
15393162788864
2199023255552
99953
Returns: 766292785
762939453125
762939453125
99984
Returns: 17707094
1525878906250
1525878906250
99900
Returns: 931249242
470184984576
470184984576
99933
Returns: 668240067
7993144737792
940369969152
99940
Returns: 449300618
678223072849
678223072849
99972
Returns: 231515398
10173346092735
2034669218547
99930
Returns: 934345133
549755813888
549755813888
99966
Returns: 367291238
7146825580544
2748779069440
99930
Returns: 130169538
282429536481
282429536481
99904
Returns: 515864127
3671583974253
1129718145924
99976
Returns: 353372279
1000000000000
1000000000000
99943
Returns: 840189460
8000000000000
3000000000000
100000
Returns: 219242311
285311670611
285311670611
99993
Returns: 471762211
855935011833
855935011833
99942
Returns: 890074736
743008370688
743008370688
99912
Returns: 871898152
9659108818944
3715041853440
99965
Returns: 572957628
1792160394037
1792160394037
99969
Returns: 245695261
17921603940370
3584320788074
99983
Returns: 840850316
289254654976
289254654976
99929
Returns: 209517553
3471055859712
867763964928
99960
Returns: 548211393
576650390625
576650390625
99995
Returns: 96721969
2883251953125
2883251953125
99977
Returns: 398519017
1099511627776
1099511627776
99945
Returns: 124571092
12094627905536
3298534883328
99971
Returns: 861358034
118587876497
118587876497
99933
Returns: 296459734
1541642394461
237175752994
99961
Returns: 441156670
198359290368
198359290368
99939
Returns: 836309482
2777030065152
793437161472
99993
Returns: 359250440
322687697779
322687697779
99966
Returns: 658761419
2904189280011
645375395558
99980
Returns: 26513846
512000000000
512000000000
99926
Returns: 757535253
7168000000000
2560000000000
99932
Returns: 194152753
1406408618241
1406408618241
99977
Returns: 961168935
8438451709446
7032043091205
99901
Returns: 452247058
230539333248
230539333248
99921
Returns: 609539219
922157332992
461078666496
99934
Returns: 604961026
506623120463
506623120463
99965
Returns: 128974530
8612593047871
2533115602315
99946
Returns: 698618893
28153056843
28153056843
99997
Returns: 980182037
84459170529
112612227372
99982
Returns: 510803483
96947540496
96947540496
99977
Returns: 828721769
1648108188432
387790161984
99902
Returns: 294625624
7774159141
7774159141
99973
Returns: 353126275
69967432269
23322477423
99944
Returns: 904787122
414000409
414000409
99955
Returns: 112138016
2898002863
1242001227
99960
Returns: 5737867
19010825718306977
707438024590
99958
Returns: 279806881
59499208480150737
663746360070
99949
Returns: 493893394
98711735140505071
972054062688
99953
Returns: 801185840
13409747300303942
215781006843
99900
Returns: 362068096
11316603097758443
997293416771
99940
Returns: 491438556
71637984340682354
358686081904
99966
Returns: 705640842
61749186983585807
135399330168
99971
Returns: 693194792
60937885587055743
476243325325
99971
Returns: 293706081
44388648634611320
142672792140
99916
Returns: 522063838
24115660560617282
737213539850
99949
Returns: 903033601
87840696670704570
378369654424
99912
Returns: 731883925
42708065234028847
868485673032
99942
Returns: 310047367
77882607592023592
223455308678
99998
Returns: 546147838
97139991962664747
840250708886
99936
Returns: 699137398
44441075642444523
713360471724
99933
Returns: 594707923
86767911974314524
145377977408
99961
Returns: 227164187
91099115717248592
537140329685
99933
Returns: 778009360
97383498587853834
787684117327
99926
Returns: 571789792
79953336572312375
713861475281
99919
Returns: 693236737
12189138147314033
288897504382
99970
Returns: 875731000
1
1
100000
Returns: 720322621
55021677489
55021677489
99945
Returns: 472966788
220086709956
275108387445
99945
Returns: 848499787
11949390190521
11949390190521
83686
Returns: 610846426
191190243048336
47797560762084
20917
Returns: 926137458
4609068800955129
4609068800955129
216
Returns: 466189889
64526963213371806
23045344004775645
40
Returns: 687746831
322499191800955129
322499191800955129
3
Returns: 766162649
736183429347170
16422268791044943
58
Returns: 935212420
284890970
325487013176021
2899
Returns: 892152820
216270127221750
1420427556996859
698
Returns: 236333110
476867675781250
3165954216741269
305
Returns: 199169603
899319296634638
21015475968381431
42
Returns: 183218063
85067466044537792
23926474188241083
35
Returns: 379933554
26847971947416142
15252082398998320
61
Returns: 6314547
99151359696222286
150891210311414393
4
Returns: 25034756
371900061473792
143711190043887872
5
Returns: 239944514
15438497005245002
8793462521246574
99
Returns: 37084157
21638337897896000
115050601771855449
8
Returns: 222726945
6114250482430934
44898398893511259
19
Returns: 118016616
16526622735126008
19829914820664332
45
Returns: 154314241
2942649737000000
53604143946081760
17
Returns: 120289048
19969028643200000
12376411500816325
72
Returns: 72374034
3504787895808
172109792742812424
5
Returns: 334008037
137231006680
12675449595860532
72
Returns: 693256984
4398046511104
4031505500287
90882
Returns: 34368953
99823692952832382
22778217820536967
39
Returns: 713059649
23179525191352
86237791782404469
10
Returns: 989847528
52523351300
33115822462536227
27
Returns: 701567142
1630436461403698
3173332710114216
313
Returns: 697904404
62777078
50365235235103053
19
Returns: 134772414
63805691337342977
105532288897483337
7
Returns: 627662209
23860872906418944
146364114031806550
5
Returns: 138123650
13753248905491290
55687934571517048
17
Returns: 243142165
1248199887663000
178306956310788
5591
Returns: 617566725
22582556622
360092841176527224
2
Returns: 619216966
2366369237643840
36875689565421006
25
Returns: 828799229
31059140149907710
97112617833804521
9
Returns: 479729243
1472283627102554
42815488374224723
22
Returns: 101143851
34165588961549
25098427228241
37893
Returns: 825139661
22145259542492192
217980958894255532
4
Returns: 124264174
985826706403392688
1
100000
Returns: 178975454
968797181919199234
1
100000
Returns: 606693401
988476778194799792
1
100000
Returns: 791649537
963354501121900082
1
100000
Returns: 200339710
963354501121900082
1
100000
Returns: 200339710
999999999999900001
1
100000
Returns: 753650017
995009990004949000
1
100000
Returns: 163865478
984930291881740849
1
100000
Returns: 445757783
988476778194799792
1
100000
Returns: 791649537
999909945163893901
1
100000
Returns: 745799889
984930292874177392
1
100000
Returns: 664328022
999999999999900001
1
100000
Returns: 753650017
999999998999950000
1
100000
Returns: 4124964
985833830252294320
1
100000
Returns: 390912055
984930291881990896
1
100000
Returns: 173742161
999909945163893902
1
100000
Returns: 745899889
999901770412331457
1
100000
Returns: 357323972
988476778194799792
1
100000
Returns: 791649537
984930291897493810
1
100000
Returns: 884532570
999997000003949998
1
100000
Returns: 77437365
985826706403392688
1
100000
Returns: 178975454
913517247483590998
1
100000
Returns: 800648188
963354674848504738
1
100000
Returns: 280950361
999999999999900001
1
100000
Returns: 753650017
984930292874177392
1
100000
Returns: 664328022
984930291881740850
1
100000
Returns: 445857783
944322726573063344
1
100000
Returns: 91317442
996622828636192242
1
100000
Returns: 356762482
999909945163893902
1
100000
Returns: 745899889
999910008256219042
1
100000
Returns: 798969598
900000000000000000
2
100000
Returns: 2154965
999999998000000000
1
100000
Returns: 254649864
989999999999999999
1
100000
Returns: 753463229