TopCoder problem "InfiniteSequence" used in SRM 413 (Division II Level Three)



Problem Statement

    

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.



Let's consider an infinite sequence A defined as follows:

  • A0 = 1;
  • Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)

You will be given n, p and q. Return the n-th element of A (index is 0-based).
 

Definition

    
Class:InfiniteSequence
Method:calc
Parameters:long, int, int
Returns:long
Method signature:long calc(long n, int p, int q)
(be sure your method is public)
    
 

Notes

-[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.
 

Constraints

-n will be between 0 and 10^12, inclusive.
-p and q will both be between 2 and 10^9, inclusive.
 

Examples

0)
    
0
2
3
Returns: 1
A[0] = 1.
1)
    
7
2
3
Returns: 7
A[0] = 1;

A[1] = A[0] + A[0] = 2;

A[2] = A[1] + A[0] = 2 + 1 = 3;

A[3] = A[2] + A[1] = 3 + 2 = 5;

A[7] = A[3] + A[2] = 5 + 3 = 8.
2)
    
10000000
3
3
Returns: 32768
3)
    
256
2
4
Returns: 89
4)
    
1
1000000
1000000
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13504&pm=9837

Writer:

yuhch123

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming