문제 설명

무한 수열 $A$는 다음과 같다.

• $A_0 = 1$
• $A_i = A_{\lfloor i/P \rfloor} + A_{\lfloor i/Q \rfloor}$

정수 $N$, $P$와 $Q$가 주어졌을 때, $A_N$을 구하는 프로그램을 작성하시요.
(단, $0 \le N \le 10^{12}$ 이고, $2 \le P, Q \le 10^9$ 이다.)

사고 과정

1. 문제가 딱 봐도 재귀적으로 주어져 있으므로, 재귀 함수를 사용하자.
2. 그런데 재귀 트리에서 중복되는 문제가 존재하므로, 메모이제이션이 필요하다.
3. 상태 공간 범위가 매우 넓다$(2 \le P, Q \le 10^9)$. 해시로 DP 하자.

시간 복잡도

1. DP 없이 푼 경우

$\min(P,Q)=X$라 두면, DP 없는 풀이의 시간 복잡도 함수는 다음과 같은 형태로 나타낼 수 있다.

$T(N)=2 \times T(N/X) + 1$

이러한 형태의 점화식은 마스터 정리로 시간 복잡도를 알아낼 수 있다.

잘 적용해서 계산하면 $O(N^{\log_{\min(P,Q)} 2})$ 가 나온다.
최대 $O(N^1)$ 이라서 시간 초과. $(N \le 10^{12})$

2. DP 적용한 경우

정답 코드 링크

$i$번 다음에는 $\lfloor i/P \rfloor$ 하고 $\lfloor i/Q \rfloor$ 의 2개의 상태 공간을 방문해야 한다.
이를 $i=0$이 될 때까지 반복해야 하므로, 최대 $\log_P N + \log_Q N$ 개의 공간이 있을 것이다.
메모이제이션 덕분에 각 상태 공간을 1번씩만 방문하므로, 시간 복잡도는 $O(\log N)$ 이 된다.

실수한 점

함수 형식인자에 int 쓰고 실인자에는 long long 전달하는 실수를 저질렀다.
long long 쓰는 문제는 반드시 제출 전에 Ctrl+F 로 모든 int를 찾아 바꿔서 제출하자.

이것 때문에 푸는데 10분 넘게 걸렸음.