Statistics

Problem Statement for "NiceMultiples"

Problem Statement

Consider all multiples of a positive integer M that do not exceed U. If we write each of them in base B, how many of them don't contain any zeros? Return the answer modulo 10^9 + 7.

Definition

Class:
NiceMultiples
Method:
count
Parameters:
long, long, int
Returns:
int
Method signature:
int count(long M, long U, int B)
(be sure your method is public)

Constraints

  • M will be between 1 and 10^12, inclusive.
  • U will be between M and 10^12, inclusive.
  • B will be between 2 and 16, inclusive.

Examples

  1. 1

    100

    2

    Returns: 6

    The multiples of 1 that do not contain any zeros in base 2 are the numbers 1, 3, 7, 15, 31, and 63. (In base 2, these are 1, 11, 111, 1111, 11111, and 111111.)

  2. 6

    123456789

    3

    Returns: 0

    In base 3, each multiple of 6 ends in a zero.

  3. 2

    117

    10

    Returns: 43

  4. 3333333333

    9999999999

    10

    Returns: 3

    Watch out for integer overflow.

  5. 1

    100000000000

    10

    Returns: 303691814

    The answer is (9 + 9^2 + ... + 9^11) modulo (10^9 + 7).

  6. 47

    47

    10

    Returns: 1

  7. 407

    407

    10

    Returns: 0

  8. 1

    1

    16

    Returns: 1

  9. 16

    32

    16

    Returns: 0

  10. 3721

    394936

    4

    Returns: 8

  11. 3

    187

    14

    Returns: 58

  12. 403

    425

    7

    Returns: 1

  13. 1919

    323399

    5

    Returns: 39

  14. 25

    3563

    14

    Returns: 117

  15. 32387045

    922820418

    11

    Returns: 15

  16. 3

    266522581

    3

    Returns: 0

  17. 692553

    7147122712

    14

    Returns: 5789

  18. 784819

    7785046

    3

    Returns: 0

  19. 24

    7155782

    9

    Returns: 102624

  20. 180934421

    332855215

    5

    Returns: 0

  21. 3

    80907503868

    9

    Returns: 702604933

  22. 68

    465655755

    13

    Returns: 3930833

  23. 4

    8

    5

    Returns: 2

  24. 2

    4

    2

    Returns: 0

  25. 19206

    91990

    11

    Returns: 0

  26. 8724880

    1827646819

    15

    Returns: 93

  27. 1521

    6143

    14

    Returns: 3

  28. 1

    29

    3

    Returns: 14

  29. 15718859

    14834267013

    14

    Returns: 540

  30. 1634

    3667021

    14

    Returns: 1441

  31. 53

    57

    16

    Returns: 1

  32. 95141

    31677767

    6

    Returns: 59

  33. 2923

    10410

    9

    Returns: 0

  34. 6286

    24548

    11

    Returns: 3

  35. 8

    15312

    3

    Returns: 100

  36. 1

    26905

    5

    Returns: 8020

  37. 1313

    6320600

    8

    Returns: 1995

  38. 6932

    9082669

    14

    Returns: 787

  39. 17863

    107810342668

    14

    Returns: 3109070

  40. 5

    415

    13

    Returns: 71

  41. 677

    677

    4

    Returns: 1

  42. 47711

    516508

    16

    Returns: 10

  43. 17

    96161467316

    11

    Returns: 227453581

  44. 129541

    19134736

    10

    Returns: 74

  45. 119

    2025

    15

    Returns: 15

  46. 230355654

    3174811122

    4

    Returns: 0

  47. 462718858

    14045088900

    13

    Returns: 14

  48. 2

    8316984411

    16

    Returns: 396192111

  49. 1

    113365914

    10

    Returns: 49644913

  50. 711935

    493167733

    5

    Returns: 0

  51. 6

    432593

    16

    Returns: 52320

  52. 368463

    2641556297

    3

    Returns: 0

  53. 450

    3325500

    10

    Returns: 0

  54. 17154235

    17154235

    16

    Returns: 0

  55. 10

    573055459

    5

    Returns: 0

  56. 3159

    31273

    4

    Returns: 0

  57. 440399

    2531106

    16

    Returns: 4

  58. 738927

    4175032933

    7

    Returns: 0

  59. 44

    9623

    10

    Returns: 143

  60. 345

    395780

    6

    Returns: 207

  61. 127

    70468052

    12

    Returns: 316032

  62. 11

    32723513

    4

    Returns: 115414

  63. 6

    31987

    13

    Returns: 3919

  64. 1

    2937

    15

    Returns: 2562

  65. 7

    797

    12

    Returns: 96

  66. 244

    426586211

    12

    Returns: 696698

  67. 1

    6901

    2

    Returns: 12

  68. 2

    733886153

    7

    Returns: 81769305

  69. 1701

    1688374819

    9

    Returns: 0

  70. 110506

    200011355448

    8

    Returns: 327306

  71. 363478

    455987770656

    5

    Returns: 39002

  72. 283079

    993494350717

    7

    Returns: 430054

  73. 315374

    131054560977

    13

    Returns: 202751

  74. 212612

    500041691841

    2

    Returns: 0

  75. 169150

    439335045341

    5

    Returns: 0

  76. 59424

    782246570102

    9

    Returns: 2498537

  77. 301363

    642609325029

    14

    Returns: 1024486

  78. 148141

    696629635759

    11

    Returns: 1684144

  79. 166432

    369376067545

    5

    Returns: 66697

  80. 126005

    940348419096

    14

    Returns: 3580934

  81. 220204

    304989040334

    7

    Returns: 189578

  82. 159015

    460187645341

    14

    Returns: 1420482

  83. 281834

    302910309057

    4

    Returns: 4143

  84. 287107

    473913345879

    6

    Returns: 133012

  85. 290922

    951383987731

    6

    Returns: 0

  86. 32735

    623137254906

    5

    Returns: 0

  87. 152074

    963517233130

    15

    Returns: 3271147

  88. 353297

    208156865659

    4

    Returns: 3845

  89. 261410

    319493123783

    10

    Returns: 0

  90. 354436

    859223468943

    2

    Returns: 0

  91. 313631

    593886937057

    2

    Returns: 0

  92. 211326

    428688050676

    11

    Returns: 737690

  93. 272628

    687058684673

    11

    Returns: 900219

  94. 265802

    963746880446

    7

    Returns: 448458

  95. 45245

    765257903858

    3

    Returns: 1312

  96. 184633

    348366399593

    14

    Returns: 915136

  97. 382005

    865226283309

    7

    Returns: 277130

  98. 214699

    492501085320

    2

    Returns: 0

  99. 356526

    516562424279

    3

    Returns: 0

  100. 399476

    789436773256

    12

    Returns: 571429

  101. 124332

    911800995176

    3

    Returns: 0

  102. 158589

    827796437906

    5

    Returns: 144647

  103. 362876

    395396877205

    6

    Returns: 70163

  104. 360160

    515066065717

    14

    Returns: 651293

  105. 71389

    213396220313

    7

    Returns: 411985

  106. 210083

    986964664252

    8

    Returns: 885079

  107. 86969

    361600196933

    5

    Returns: 124523

  108. 256412

    398364851325

    10

    Returns: 446679

  109. 77061

    427647994935

    15

    Returns: 2559622

  110. 258223

    818110384735

    3

    Returns: 256

  111. 225282

    130321202626

    9

    Returns: 119533

  112. 377500

    128587864776

    2

    Returns: 0

  113. 368967

    756842396689

    6

    Returns: 87649

  114. 379711

    949350874976

    11

    Returns: 886710

  115. 191967

    515449234123

    16

    Returns: 1509629

  116. 392905

    512376067678

    7

    Returns: 178294

  117. 198556

    118499328262

    6

    Returns: 40590

  118. 144538

    120728012734

    13

    Returns: 407810

  119. 288857

    317017490884

    6

    Returns: 89824

  120. 41952

    992685731076

    16

    Returns: 0

  121. 236996

    235394350505

    16

    Returns: 448691

  122. 376087

    490491066101

    14

    Returns: 642937

  123. 84262

    785637696099

    13

    Returns: 4230979

  124. 383529

    723240175642

    3

    Returns: 0

  125. 204302

    467502504915

    2

    Returns: 0

  126. 258932

    380344622325

    14

    Returns: 659508

  127. 160016

    268324667971

    16

    Returns: 0

  128. 206336

    995999100415

    13

    Returns: 0

  129. 257716

    656073276295

    5

    Returns: 73588

  130. 243492

    655396795637

    6

    Returns: 0

  131. 51669093474

    894006223612

    15

    Returns: 9

  132. 1647

    732911768212

    16

    Returns: 250047514

  133. 53

    631919663837

    11

    Returns: 228400042

  134. 564

    200198318185

    13

    Returns: 164262770

  135. 1

    846136706472

    14

    Returns: 883096778

  136. 969

    479971770364

    10

    Returns: 158762024

  137. 6

    739908088057

    2

    Returns: 0

  138. 5409968701

    619417222820

    9

    Returns: 29

  139. 11518

    741841238621

    8

    Returns: 10216787

  140. 564

    916600478716

    5

    Returns: 40614425

  141. 120480226

    150322726431

    9

    Returns: 351

  142. 6280010996

    932739982633

    11

    Returns: 47

  143. 3201141278

    324746970086

    9

    Returns: 23

  144. 671128

    138359808091

    8

    Returns: 0

  145. 1852

    185975044420

    9

    Returns: 28056944

  146. 886

    751184647064

    7

    Returns: 106136599

  147. 7449

    991159172624

    3

    Returns: 0

  148. 19553415507

    963007386254

    16

    Returns: 32

  149. 36067

    879479198005

    10

    Returns: 7739914

  150. 11

    290457947567

    5

    Returns: 849456719

  151. 242199

    737912986928

    7

    Returns: 388353

  152. 79

    475796092067

    15

    Returns: 244840653

  153. 104857

    730385225902

    6

    Returns: 490471

  154. 3

    643901319172

    7

    Returns: 479159039

  155. 19

    797695989395

    10

    Returns: 371841769

  156. 3059

    816903160528

    9

    Returns: 67795262

  157. 1

    121461558156

    8

    Returns: 34801933

  158. 405949375

    222199637120

    6

    Returns: 39

  159. 267177755

    498081032997

    5

    Returns: 0

  160. 4

    852717464635

    12

    Returns: 572694225

  161. 12413778301

    852216911853

    11

    Returns: 26

  162. 244398834

    335826399206

    16

    Returns: 730

  163. 64

    298976790786

    15

    Returns: 529764913

  164. 3961309

    692317710530

    10

    Returns: 55684

  165. 15849406670

    861856565674

    11

    Returns: 22

  166. 3957864

    823319346550

    8

    Returns: 0

  167. 1616

    706059610075

    4

    Returns: 0

  168. 44558160844

    174888428686

    6

    Returns: 0

  169. 800213291

    646324400068

    12

    Returns: 338

  170. 235

    1000000000000

    11

    Returns: 515366432

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: