TopCoder problem "BunnySequence" used in SRM 487 (Division I Level Three)



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)
    
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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10761

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14240&pm=10761

Writer:

lyrically

Testers:

PabloGilberto , ivan_metelsky , soul-net

Problem categories:

Dynamic Programming