BunnySequence
SRM 487 · 2010-03-12 · by lyrically
SRM 487 · 2010-03-12 · by lyrically · Dynamic Programming
Problem Statement
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,
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.
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.
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.
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)
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
1)
487 0 Returns: 1
B0 = 1 means x = 1.
2)
19 10 Returns: 512
3)
3 4 Returns: 6
4)
10 487 Returns: 829515032
5)
961028 988908 Returns: 1000000007
answer = MOD - 2
6)
956197 966003 Returns: 1000000008
answer = MOD - 1
7)
967981 985323 Returns: 0
answer = 0
8)
951496 980267 Returns: 1
answer = 1
9)
948272 954547 Returns: 2
answer = 2
Submissions are judged against all 86 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BunnySequence with a public method int getNumber(int m, int n) · 86 test cases · 2 s / 256 MB per case