====== 무한 수열 ======

===== 풀이 =====
  * 점화식이 주어진 상태에서 구현만 하면 된다. 바텀업으로 바꿔서 처리하기는 복잡하고 비효율적이고, 그냥 저대로 재귀함수를 만들고 memoization을 추가해주면 된다.
  * 시간복잡도 계산은 좀 어려운데.. 대충 x=min(p,q)를 x라 하고 T(n)=2*T(n/x)+c 라고 하면.. 마스터정리를 적용해서 $ O(n^{log_x{2}}) $ 처럼 구할수 있을거 같다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1351. 무한 수열".

- Problem link: https://www.acmicpc.net/problem/1351
- Solution link: http://www.teferi.net/ps/problems/boj/1351
"""

import functools


@functools.cache
def calc(n, p, q):
    if n == 0:
        return 1
    return calc(n // p, p, q) + calc(n // q, p, q)


def main():
    N, P, Q = [int(x) for x in input().split()]
    print(calc(N, P, Q))


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:골드_5}}