TopCoder Statistics - Problem Statement

Problem Statement

Given is a positive integer W. We will use W to define a function f. The value f(x) is computed as follows:

If x is not a positive integer, f(x) is undefined.
Let y = x modulo W. If y is zero, f(x) is undefined.
Otherwise, f(x) = x/y (where "/" denotes exact real division).

For any positive integer x, consider the following infinite sequence: x, f(x), f(f(x)), f(f(f(x))), and so on. We say that f is always defined for x if all the terms of the above sequence are defined. (In other words, there is no positive integer k such that f^k(x) is undefined. Here, f^k denotes f applied k times.)

You are given longs L and R, and the int W used in our function f. Count all x between L and R, inclusive, such that f is always defined for x. Return that count.

Definition

Class:: AlwaysDefined
Method:: countIntegers
Parameters:: long, long, int
Returns:: long
Method signature:: long countIntegers(long L, long R, int W)
(be sure your method is public)

Constraints

L will be between 1 and 10^18, inclusive.
R will be between L and 10^18, inclusive.
W will be between 2 and 3000, inclusive.

Examples

10

10

4

Returns: 1

For W = 4, we have f(10) = 5, f(f(10)) = 5, f(f(f(10))) = 5 and so on, thus f is always defined for x = 10.
1

99

2

Returns: 50

For W = 2, f is always defined for odd integers but not for even integers. There are 50 odd integers between 1 and 99, inclusive.
1282

1410

10

Returns: 42
29195807

273209804877

42

Returns: 31415926535
1

1

2

Returns: 1
1

1

3000

Returns: 1
1000000000000000000

1000000000000000000

2

Returns: 0
1000000000000000000

1000000000000000000

3000

Returns: 1
1

1000000000000000000

2

Returns: 500000000000000000
100000000000000000

999999999999999999

2

Returns: 450000000000000000
64

81

6

Returns: 9
50

75

6

Returns: 14
26

77

8

Returns: 19
942

980

10

Returns: 12
308

775

9

Returns: 152
99

410

5

Returns: 130
7486

7638

5

Returns: 64
3460

8138

2

Returns: 2339
6511

6583

4

Returns: 36
1242

5114

5

Returns: 1614
5

6

1673

Returns: 2
4

9

1156

Returns: 6
4

5

410

Returns: 2
50

68

2084

Returns: 19
21

46

494

Returns: 26
68

72

2587

Returns: 5
446

531

4

Returns: 43
140

928

2905

Returns: 789
242

639

2278

Returns: 398
4122

9220

88

Returns: 337
2343

9399

1454

Returns: 22
3628

9941

1600

Returns: 118
45646

86269

2735

Returns: 124
42354

51764

356

Returns: 237
33660

98871

1735

Returns: 335
459751

886335

14

Returns: 107081
162233

913075

2010

Returns: 8334
633235

713334

2101

Returns: 399
5161275

7869877

1745

Returns: 12509
6440204

8877767

735

Returns: 24510
2428783

6412109

2220

Returns: 18359
31718851

65933933

172

Returns: 1162121
21383404

87851131

2276

Returns: 242928
21678516

88513601

699

Returns: 684066
399504230

962878994

1840

Returns: 2513362
718743433

791183264

2986

Returns: 208246
360845077

858156754

739

Returns: 4833043
1720953622

8809320805

2876

Returns: 21082006
4899946290

8558624064

2245

Returns: 13535983
3259932498

9147190036

2874

Returns: 17536394
34305813784

82093251803

465

Returns: 702560394
26193839819

81805155138

415

Returns: 891522209
60564329991

75607908600

1241

Returns: 93663948
507916444822

586526822612

2055

Returns: 315210770
594579466666

853027852402

1840

Returns: 1150040576
115116373693

175533454148

1750

Returns: 280607085
5252951622624

8382125970798

409

Returns: 50416490697
5786257107427

8720918713340

313

Returns: 59272856456
4029244507721

5176336815919

1454

Returns: 6207541401
16664446265797

40188378941129

1554

Returns: 121282626781
9823889497864

31939751215783

2276

Returns: 80859921195
59153359432813

96281270049710

174

Returns: 1262893153091
636805763926153

826467848292361

374

Returns: 3362054653074
312752144974739

797883501700719

2465

Returns: 1658390532777
43201258552815

830177614215010

457

Returns: 11539113252678
7105878033852218

8654418918115636

2814

Returns: 4717359669111
3074761494535501

9270789671576691

2531

Returns: 20596439453858
2126199246766219

7447930262201672

333

Returns: 103627331545586
6630810962025080

68909235472530139

728

Returns: 626561708982298
16632339031204305

26131538821724743

2910

Returns: 28079194214047
46667853158204524

82349122162409151

1905

Returns: 152963010165369
323962717863940419

492043940623002396

2918

Returns: 493119572587669
170436188555171928

929588805816446517

2612

Returns: 2458128232282225
9513157309626853

503497456212196863

162

Returns: 18012292863869895
52654107011850814

744472477227325439

2028

Returns: 2819463395911898
192990419302183729

720417743043986124

495

Returns: 7420152550452598
341456639534498849

624799101542923741

2418

Returns: 987943030975712
372026864778142498

721018830199145678

870

Returns: 2999646026426202
756694937695243209

843113013265710484

169

Returns: 2944885624688831
22759481828843112

783671881054252438

1173

Returns: 5000090560052679
757612502946103286

874411200133228655

280

Returns: 2719727607389093
388887627684673869

573590534997501244

2438

Returns: 636911238416078
647011837983188253

713312361254123341

1567

Returns: 335683517716937
136297032681818299

949933673066964381

546

Returns: 10545645320739125
783038641386851558

903243786439648877

2193

Returns: 455438213020720
117612424329528178

964292682939478837

2592

Returns: 2786402851933116
421028798206710645

746439041422957899

2533

Returns: 1082851273689598
59752679420928510

673305103776871826

1612

Returns: 3055075831715670
52298379892529957

269625691670571708

894

Returns: 1804179825278701
381925450494943557

627028125654228102

197

Returns: 7288232774764183
356635585102675146

395858675747098991

2218

Returns: 146563496008439
1

1000000000000000000

2730

Returns: 3151942850496260
645047798073084306

811752679427757911

2730

Returns: 525444258676703
748634606658351508

763878138651190648

2730

Returns: 48046741657269
577645968463684467

600964509217205319

2730

Returns: 73498707777343
1406397922093

999992882424122323

2730

Returns: 3151915983071781
1

1000000000000000000

2310

Returns: 3659684934997893
433628486269518541

996994145646241055

2310

Returns: 2061740815761290
336604459751163452

988718863354912044

2310

Returns: 2386533257904548
271333478698776887

633235251612756440

2310

Returns: 1324446465838624
7767641210996

999992045242878331

2310

Returns: 3659627395503510
1

1000000000000000000

2520

Returns: 3400443295134379
593393321383405202

718851487851131587

2520

Returns: 426613380853552
136016962878996361

678516399504228604

2520

Returns: 1844738571364833
183264636084507788

874343385815675491

2520

Returns: 2349974100240825
7209536224899

999990932080528558

2520

Returns: 3400387944129251
1

1000000000000000000

2772

Returns: 3111020242498177
624064914719003703

946290932599322823

2772

Returns: 1002451664004244
209325180326194550

430581378418179969

2772

Returns: 688332510862976
513860564329991758

819375607908600507

2772

Returns: 950463484697799
6526822612594

999999164448229853

2772

Returns: 3110997337647441
1

1000000000000000000

2640

Returns: 3252468029454598
27852402175535522

579466666011511022

2640

Returns: 1794107757325938
148983821259708757

369352529516224483

2640

Returns: 716742178136829
578625710742740292

720918713340851763

2640

Returns: 462803441654871
4450772104018

999993681591916664

2640

Returns: 3252433002719297
1

1000000000000000000

2940

Returns: 2950519124417857
446265797409824281

837894112931937403

2940

Returns: 1155506834290061
215783196281270208

497864591533593481

2940

Returns: 832286551111214
132636805763926153

710826467848292361

2940

Returns: 1705959655059321
4797883501700

999993127521449747

2940

Returns: 2950484690476842
1

1000000000000000000

2340

Returns: 3618969959653823
391830177614215862

719043201258552467

2340

Returns: 1184174102745796
686544189181156801

710587803385221843

2340

Returns: 87013117508252
74761494535501421

270789671576691744

2340

Returns: 709420083846945
2619924676621

999997930262201672

2340

Returns: 3618952987631699
1

1000000000000000000

1980

Returns: 4202087061317763
906630810962025601

968909235472530125

1980

Returns: 261699361787489
261315388217247808

516632339031203359

1980

Returns: 1072864055386238
466678531582045240

823491221624091514

1980

Returns: 1499357987882731
3239627178639

999999204394062300

1980

Returns: 4202070104644468
1

1000000000000000000

2970

Returns: 2921574369594539
239689295888058722

404191704361885437

2970

Returns: 480606020216274
465175034974562221

719280009513156446

2970

Returns: 742386580613921
626853052654107011

968630744472477227

2970

Returns: 998528944261961
8508149192990

999993254397204177

2970

Returns: 2921529804309944
1

1000000000000000000

2100

Returns: 3986847223609430
419302183729342201

430439861244624784

2100

Returns: 44404218672534
101542923741722402

639534498849936986

2100

Returns: 2144890217241081
686477814249884311

830199145678175669

2100

Returns: 572994991080188
3013265710484

999994937695243209

2100

Returns: 3986815027281305
1

1000000000000000000

2856

Returns: 3024118982687601
22759481828843181

178367188105424811

2856

Returns: 470576218340318
787441120013324355

875761250294609284

2856

Returns: 267090582471482
557359053499750124

633888876276846738

2856

Returns: 231435289746233
6964701183798

999994571331236125

2856

Returns: 3024081503359522
1

1000000000000000000

1680

Returns: 4873987062510354
318825351362970481

412334194993367185

1680

Returns: 455760894034933
696438159032437922

818182997830385040

1680

Returns: 593382769150093
396488779642926829

868515583117612424

1680

Returns: 2300652533002283
3295281784210

999993947883727464

1680

Returns: 4873941503177997
1

1000000000000000000

840

Returns: 9010349069985582
287982067106458202

390414229578996525

840

Returns: 922949539839728
51037768718268361

752679420928509480

840

Returns: 6322036208247880
298379892529957662

625691670571708381

840

Returns: 2949193374770165
7028125654228

999999254504949435

840

Returns: 9010279026819645
1

1000000000000000000

90

Returns: 61871444915812262
102356635585102681

570395858675747056

90

Returns: 28958263009888604
146222607358698923

991079103133496274

90

Returns: 52272492140089239
557714421256074326

908567796049401532

90

Returns: 21707805252048993
339606500572

999991157009826132

90

Returns: 61870876775283943
1

1000000000000000000

3000

Returns: 2891845368637156
669043657448791799

751284264247887023

3000

Returns: 237827117861064
585911319688163273

712681148824779000

3000

Returns: 366598743234362
6021298353306931

867024840623385859

3000

Returns: 2489889105897107
3786983680032

999996614940253133

3000

Returns: 2891824628055542
1

1000000000000000000

2999

Returns: 2861981697948990
238664216962355857

974474930310087168

2999

Returns: 2105876794754841
576821941946455995

785307162462091887

2999

Returns: 596680885408256
122788058602715378

452503894940439897

2999

Returns: 943640689121978
4021222182963

999990919703095001

2999

Returns: 2861944201639609
1

1000000000000000000

2998

Returns: 2864512913722216
766953106159975540

961007546344782301

2998

Returns: 555871449872756
664796127739009245

829110669461474246

2998

Returns: 470681126674932
171838283367932581

613567810250512324

2998

Returns: 1265339934123579
8237885633862

999992647783630781

2998

Returns: 2864468255666822
1

1000000000000000000

2997

Returns: 2876001709044161
164503257809635630

364478219338354340

2997

Returns: 575128331114444
406922274720549128

594500739104022039

2997

Returns: 539475984139228
48008678989728228

585664024224389022

2997

Returns: 1546297691749788
3046606777372

999991913434912282

2997

Returns: 2875969689996479
1

1000000000000000000

2996

Returns: 2876677100674611
6773911002597661

43771536850659999

2996

Returns: 106430223067925
442354310288806049

526520353554384142

2996

Returns: 242118529307057
403322471640310168

625577367192146379

2996

Returns: 639355568521851
5186467201393

999992663894275077

2996

Returns: 2876641077217342
1

1000000000000000000

2995

Returns: 2868531386467798
79420603389250824

794308814502184296

2995

Returns: 2050679271383995
734292035998631827

812406236718925263

2995

Returns: 224073036493812
157647316309365657

828551876868573481

2995

Returns: 1924510789279501
9964902521235

999990249343694753

2995

Returns: 2868474831758377
1

1000000000000000000

1600

Returns: 5036749061104985
300151597193790402

554733644783476893

1600

Returns: 1282265889161355
365426829334161921

539049974792248354

1600

Returns: 874496214865358
63513219520448308

85186242953982863

1600

Returns: 109161580429550
5035416131912

999993726796257062

1600

Returns: 5036692102394232
1

1000000000000000000

299

Returns: 21241352071872391
360454769877692569

753357977173215714

299

Returns: 8345795356331197
717331471745170596

721684075668414667

299

Returns: 92455192363041
560684446263646077

567951353217900421

299

Returns: 154358929088854
8844622974053

999999713759112180

299

Returns: 21241158119976781
1

1000000000000000000

2409

Returns: 3486458432355540
170521071660157115

197892858336767576

2409

Returns: 95430596465857
166722179138037040

681444269315169603

2409

Returns: 1794557171582064
205842274679447754

341288506935484505

2409

Returns: 472227658570628
8589384242472

999990529862117189

2409

Returns: 3486395468539463
1

1000000000000000000

817

Returns: 8958203929601342
577112790261884688

625339456011710280

817

Returns: 432024306631470
60063653238817327

474222439885809941

817

Returns: 3710118870017998
697252959152444984

698219787741238916

817

Returns: 8661047663403
5084004812539

999995770406369480

817

Returns: 8958120496483330
1

1000000000000000000

2983

Returns: 2879927367255733
307389364579448143

732374880029441814

2983

Returns: 1223927416625113
449451221696247523

487215973110304997

2983

Returns: 108759741114382
690850095770186889

895293036402016763

2983

Returns: 588780819764449
9582231921282

999993284212796571

2983

Returns: 2879880430132953
1

1000000000000000000

1000

Returns: 7598429102818758
527851806991997001

876744467886936584

1000

Returns: 2651036148296589
179134104484838002

796485668003277286

1000

Returns: 4690902086895557
205788847135365756

844421322824192165

1000

Returns: 4852603589265135
49589906218

999997498703506535

1000

Returns: 7598409720077148
1

1000000000000000000

206

Returns: 28885826171051603
474232376373046386

550301428451667195

206

Returns: 2197317415339648
204427418244633192

349265799771842399

206

Returns: 4183776311691262
374526003384944958

703671530573528016

206

Returns: 9507640483348253
993165644467

999997240385657563

206

Returns: 28885717768900658
1

1000000000000000000

305

Returns: 20846395345984755
106160366825906206

954870352469418336

305

Returns: 17692543894808047
671942859610226752

845778508577048133

305

Returns: 3623846663587863
635075025742754851

817824344753256383

305

Returns: 3809664553301994
9466676761243

999997862195273305

305

Returns: 20846153434374327
1

1000000000000000000

1662

Returns: 4826693540643633
49833200206779692

781842918095198517

1662

Returns: 3533186576999905
602862699717246247

813536016869970338

1662

Returns: 1016855539080168
295321103158854137

556511931562866928

1662

Returns: 1260688084325474
1545814755157

999999409469453635

1662

Returns: 4826683229141510
1

1000000000000000000

1847

Returns: 4384549491833420
387122335398995624

420223582661772744

1847

Returns: 145134056865047
520789976390245697

957467975087083327

1847

Returns: 1914636297280709
166331234910979459

506850625014626038

1847

Returns: 1493024118838099
9109932480692

999991984010355472

1847

Returns: 4384474402379330
94351468238719855

943514682387198550

2520

Returns: 2887531357190438
300000001

1000000000000000000

3000

Returns: 2891845367727397
29195807

273209804877

2520

Returns: 929119892
1

1000000000000000000

1972

Returns: 4167986182644552

Statistics

Problem Statement for "AlwaysDefined"

Problem Statement

Definition

Constraints

Examples