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 |
| 0) | |
| | | 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
|
|
|
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |