TopCoder problem "InfiniteSequence2" used in SRM 413 (Division I Level Two)



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:

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

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

Definition

    
Class:InfiniteSequence2
Method:calc
Parameters:long, int, int, int, int
Returns:long
Method signature:long calc(long n, int p, int q, int x, int y)
(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^13, inclusive.
-p and q will both be between 2 and 10^9, inclusive.
-x and y will both be between 0 and 10^9, inclusive.
 

Examples

0)
    
10000000
2
3
10000000
10000000
Returns: 2
A[10000000] = A[-5000000] + A[-6666667] = 2.
1)
    
12
2
3
1
0
Returns: 8
2)
    
0
2
2
0
0
Returns: 1
A[0] = 1.
3)
    
123
45
67
8
9
Returns: 2

Problem url:

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

Problem stats url:

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

Writer:

yuhch123

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming