InfiniteSequence2

문제

무한수열 A 가 있다

i<=0 일때 Ai = 1
i>=1 일때 Ai = A[i/p]-x + A[i/q]-y 가 된다

[x] 는 x 의 내림함수를 의미한다
(ex. [3.4] = 3, [0.6] = 0)

n p q x y 가 주어질때 A의 n 번째 요소를 리턴한다 (인덱스는 0-based)

n : 0 이상, 10^13 이하
p,q : 2 이상, 10^9 이하
x,y : 0 이상, 10^9 이하

예시 입력

50, 2, 3, 4, 1
10000000, 2, 3, 10000000, 10000000
12, 2, 3, 1, 0
0, 2, 2, 0, 0
124, 45, 67, 8, 9

예시 출력

10
2
8
1
2

생각의 변화

Ai 부터 아래로 트리가 구성되므로, 깊이우선탐색으로 Ai 값을 획득할수 있다

다만, n 이 10^13 까지 가능하므로, 그대로 재귀함수를 사용하면 문제가 될것 같다

pseudo code

dfs(i)
    if i <= 0
    	return 1
        
    return dfs(floor(i/p) - x) + dfs(floor(i/q) - y)
    
calc(n, p, q, x, y)
    
    this->p = p
    this->q = q
    this->x = x
    this->y = y
    
    return dfs(n)

caveat

예시 입력에서는 10^13 이 없으므로 그대로 통과되었으나,
메모화 재귀를 사용해서 계산량을 줄여야 한다.