Statistics

Problem Statement for "DivisibleSequence"

Problem Statement

A divisible sequence with starting value N and length H is a sequence of positive integers with the following properties:
  • The sequence has H elements, labeled A[0] through A[H-1].
  • A[0] equals N.
  • For each i between 0 and H-2, inclusive, A[i+1] divides A[i].
You are given the ints N and H. Let C be the count of all divisible sequences with starting value N and length H. Return the value (C modulo 1,000,000,009).

Definition

Class:
DivisibleSequence
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int N, int H)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.
  • H will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 5

    3

    Returns: 3

    The three possible sequences are: 5, 5, 5 5, 5, 1 5, 1, 1

  2. 6

    3

    Returns: 9

    The nine possible sequences are: 6, 6, 6 6, 6, 3 6, 6, 2 6, 6, 1 6, 3, 3 6, 3, 1 6, 2, 2 6, 2, 1 6, 1, 1

  3. 10

    2

    Returns: 4

    A[1] can be equal to each of the divisors of the number 10. That is, A[1] can be 1, 2, 5, or 10.

  4. 1

    10000

    Returns: 1

    The only possible sequence consists of all ones.

  5. 30

    4

    Returns: 64

  6. 25883

    100000

    Returns: 991000009

  7. 647407371

    1

    Returns: 1

  8. 110174988

    1

    Returns: 1

  9. 4491883

    1

    Returns: 1

  10. 1000000000

    1000000000

    Returns: 1

  11. 128

    5

    Returns: 330

  12. 1024

    6

    Returns: 3003

  13. 8192

    9

    Returns: 203490

  14. 65536

    10

    Returns: 2042975

  15. 524288

    5

    Returns: 8855

  16. 4194304

    3

    Returns: 276

  17. 33554432

    5

    Returns: 23751

  18. 268435456

    10

    Returns: 124403620

  19. 607227212

    1000000000

    Returns: 2916

  20. 570657782

    1000000000

    Returns: 999999280

  21. 31720467

    1000000000

    Returns: 81

  22. 616277956

    1000000000

    Returns: 999973765

  23. 392090393

    1000000000

    Returns: 999999280

  24. 947786970

    1000000000

    Returns: 999940960

  25. 889463010

    1000000000

    Returns: 6561

  26. 656296092

    1000000000

    Returns: 999988345

  27. 724618275

    1000000000

    Returns: 999973765

  28. 74424508

    1000000000

    Returns: 2916

  29. 223092870

    1000000000

    Returns: 612579520

  30. 892371480

    1000000000

    Returns: 384075472

  31. 528377850

    1000000000

    Returns: 392922434

  32. 618072047

    241039583

    Returns: 241039583

  33. 417666895

    31398275

    Returns: 664102966

  34. 913560619

    607018036

    Returns: 607018036

  35. 575330186

    810777402

    Returns: 677629703

  36. 645533998

    833377033

    Returns: 881227641

  37. 358206437

    268814082

    Returns: 268814082

  38. 508497218

    186401907

    Returns: 620525619

  39. 736093901

    617502990

    Returns: 617502990

  40. 280465279

    469507421

    Returns: 469507421

  41. 871828149

    829804015

    Returns: 112947952

  42. 847424561

    28145410

    Returns: 28145410

  43. 861162853

    898614095

    Returns: 898614095

  44. 388916998

    598567553

    Returns: 279859801

  45. 891660971

    260561351

    Returns: 260561351

  46. 993849463

    812677863

    Returns: 812677863

  47. 262777433

    770756043

    Returns: 770756043

  48. 779145303

    153589475

    Returns: 618468091

  49. 939819766

    183286708

    Returns: 27131111

  50. 536091299

    58740986

    Returns: 58740986

  51. 766216357

    596876469

    Returns: 596876469

  52. 205713660

    645989977

    Returns: 738543667

  53. 592849636

    139499967

    Returns: 69856908

  54. 934135810

    442473862

    Returns: 975777879

  55. 523164325

    581634158

    Returns: 327411676

  56. 924276981

    101871547

    Returns: 343340284

  57. 218476551

    480776573

    Returns: 65309330

  58. 87762983

    413898968

    Returns: 833463261

  59. 607627509

    309433553

    Returns: 58887685

  60. 879541585

    838282600

    Returns: 344427726

  61. 461163917

    371029704

    Returns: 11360256

  62. 134038397

    297471730

    Returns: 297471730

  63. 907279181

    220315684

    Returns: 876856448

  64. 389766571

    698901314

    Returns: 698901314

  65. 199468152

    900927383

    Returns: 880289570

  66. 921536961

    212836495

    Returns: 863869231

  67. 109827511

    528568733

    Returns: 990761171

  68. 860548627

    750775782

    Returns: 258823754

  69. 811191662

    620361885

    Returns: 271676500

  70. 850021656

    664585135

    Returns: 937075534

  71. 6801226

    99228110

    Returns: 725556147

  72. 875035561

    226034598

    Returns: 629615730

  73. 959202841

    572907596

    Returns: 586699411

  74. 803665801

    866909724

    Returns: 834436871

  75. 56806369

    871371041

    Returns: 565603683

  76. 49378729

    379535140

    Returns: 788966230

  77. 536870912

    99999963

    Returns: 916296978

  78. 536870912

    999999975

    Returns: 999721753

  79. 536870912

    999999980

    Returns: 1000000008

  80. 536870912

    999999981

    Returns: 0

  81. 536870912

    1000000000

    Returns: 0

  82. 995425200

    999999976

    Returns: 301366032

  83. 931170240

    1000000000

    Returns: 607077575

  84. 999999998

    999999998

    Returns: 999998678

  85. 123456789

    987654321

    Returns: 464723823

  86. 100000000

    100000000

    Returns: 136624515

  87. 268435456

    1000000000

    Returns: 0

  88. 12345678

    1000000000

    Returns: 999973765

  89. 999999978

    999999987

    Returns: 234256

  90. 10000

    1000000000

    Returns: 15876

  91. 999999999

    888888887

    Returns: 870111041

  92. 999999613

    999999613

    Returns: 999999613

  93. 8

    999999999

    Returns: 999999889

  94. 73513440

    1000000000

    Returns: 375025393

  95. 999999999

    999999999

    Returns: 21000

  96. 536870912

    999999999

    Returns: 0

  97. 60

    3

    Returns: 54

  98. 600000000

    28

    Returns: 625742509

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: