Statistics

Problem Statement for "BunnySequence"

Problem Statement

Bunnies like programming and they sometimes make useless devices.

One group of bunnies made a simple computer that calculates the following function f:
For a positive integer x,
  • f(x) = x / m if x is a multiple of m.
  • f(x) = x + 1 otherwise.
where m is a fixed positive integer greater than 1.

For a positive integer x, we define a sequence {Bk} by B0 = x and Bk+1 = f(Bk). Let g(x) be the smallest index k of this sequence such that Bk = 1. Calculate the number of positive integers x satisfying g(x) = n, and return the answer modulo 1,000,000,009.

Definition

Class:
BunnySequence
Method:
getNumber
Parameters:
int, int
Returns:
int
Method signature:
int getNumber(int m, int n)
(be sure your method is public)

Notes

  • For any positive integer x, there always exists k such that Bk = 1.

Constraints

  • m will be between 2 and 1,000,000, inclusive.
  • n will be between 0 and 1,000,000, inclusive.

Examples

  1. 5

    3

    Returns: 4

    There are four positive integers x such that f(f(f(x))) = 1. The sequences {Bk} for them are as follows: 3 -> 4 -> 5 -> 1 20 -> 4 -> 5 -> 1 24 -> 25 -> 5 -> 1 125 -> 25 -> 5 -> 1

  2. 487

    0

    Returns: 1

    B0 = 1 means x = 1.

  3. 19

    10

    Returns: 512

  4. 3

    4

    Returns: 6

  5. 10

    487

    Returns: 829515032

  6. 961028

    988908

    Returns: 1000000007

    answer = MOD - 2

  7. 956197

    966003

    Returns: 1000000008

    answer = MOD - 1

  8. 967981

    985323

    Returns: 0

    answer = 0

  9. 951496

    980267

    Returns: 1

    answer = 1

  10. 948272

    954547

    Returns: 2

    answer = 2

  11. 2

    0

    Returns: 1

  12. 2

    1

    Returns: 1

  13. 2

    2

    Returns: 1

  14. 2

    3

    Returns: 2

  15. 2

    4

    Returns: 3

  16. 2

    1000000

    Returns: 472063836

  17. 3

    0

    Returns: 1

  18. 3

    1

    Returns: 1

  19. 3

    2

    Returns: 2

  20. 3

    3

    Returns: 3

  21. 3

    4

    Returns: 6

  22. 3

    1000000

    Returns: 41706358

  23. 4

    0

    Returns: 1

  24. 4

    1

    Returns: 1

  25. 4

    2

    Returns: 2

  26. 4

    3

    Returns: 4

  27. 4

    4

    Returns: 7

  28. 4

    1000000

    Returns: 376808075

  29. 1000000

    0

    Returns: 1

  30. 1000000

    1

    Returns: 1

  31. 1000000

    2

    Returns: 2

  32. 1000000

    3

    Returns: 4

  33. 1000000

    4

    Returns: 8

  34. 1000000

    1000000

    Returns: 985796960

  35. 999997

    999997

    Returns: 998224627

  36. 999997

    999998

    Returns: 996449245

  37. 999997

    999999

    Returns: 992898480

  38. 999997

    1000000

    Returns: 985796949

  39. 999998

    999997

    Returns: 998224628

  40. 999998

    999998

    Returns: 996449246

  41. 999998

    999999

    Returns: 992898483

  42. 999998

    1000000

    Returns: 985796956

  43. 999999

    999997

    Returns: 998224628

  44. 999999

    999998

    Returns: 996449247

  45. 999999

    999999

    Returns: 992898484

  46. 999999

    1000000

    Returns: 985796959

  47. 1000000

    999997

    Returns: 998224628

  48. 1000000

    999998

    Returns: 996449247

  49. 1000000

    999999

    Returns: 992898485

  50. 24281

    24279

    Returns: 87869530

  51. 24281

    24280

    Returns: 175739060

  52. 24281

    24281

    Returns: 351478119

  53. 24281

    24282

    Returns: 702956238

  54. 24281

    24283

    Returns: 405912466

  55. 288

    286

    Returns: 791489584

  56. 288

    287

    Returns: 582979159

  57. 288

    288

    Returns: 165958308

  58. 288

    289

    Returns: 331916616

  59. 288

    290

    Returns: 663833231

  60. 17

    15

    Returns: 16384

  61. 17

    16

    Returns: 32768

  62. 17

    17

    Returns: 65535

  63. 17

    18

    Returns: 131070

  64. 17

    19

    Returns: 262139

  65. 99

    640524

    Returns: 871506302

  66. 2

    605659

    Returns: 558827633

  67. 435704

    482135

    Returns: 510500089

  68. 419269

    241

    Returns: 725778777

  69. 121

    58

    Returns: 778819198

  70. 1093

    4

    Returns: 8

  71. 41996

    9106

    Returns: 13897020

  72. 8

    185

    Returns: 581276265

  73. 6

    14780

    Returns: 762925915

  74. 67821

    1

    Returns: 1

  75. 1376

    29100

    Returns: 234766752

  76. 7

    776

    Returns: 435455820

  77. 1850

    2901

    Returns: 60338749

  78. 16

    5497

    Returns: 592607699

  79. 12

    1

    Returns: 1

  80. 9

    11

    Returns: 1019

  81. 999199

    999199

    Returns: 754352623

  82. 231

    42123

    Returns: 552158526

  83. 10007

    999999

    Returns: 503760399

  84. 999997

    999777

    Returns: 22025332

  85. 102407

    50000

    Returns: 642595749

  86. 1337

    1000000

    Returns: 733364532

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: