Connection Status:
Competition Arena > InfiniteSequence2

InfiniteSequence2

SRM 413 · 2008-08-05 · by yuhch123

SRM 413 · 2008-08-05 · by yuhch123 · Dynamic Programming
Class Name: InfiniteSequence2
Return Type: long
Method Name: calc
Arg Types: (long long, int, int, int, int)
Problem Statement

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

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
4)
10000000000000
2
2
0
10131990
Returns: 11993312
60)
10000000000000
2
2
0
0
Returns: 17592186044416

max answer

Submissions are judged against all 125 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class InfiniteSequence2 with a public method long long calc(long long n, int p, int q, int x, int y) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous