무한 수열
면접 대비시간 제한2초메모리 제한128 MB
A_i가 A_⌊i/P⌋와 A_⌊i/Q⌋의 합으로 정의되는 수열에서 N이 매우 커도 메모이제이션 재귀로 N번째 항을 구하는 문제입니다.
문제
무한 수열 A는 다음과 같이 정의된다.
- A_0 = 1
- i ≥ 1일 때, A_i = A_⌊i / P⌋ + A_⌊i / Q⌋
정수 N, P, Q가 주어질 때 A_N을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 N, P, Q가 공백으로 구분되어 주어진다.
출력
A_N의 값을 출력한다.
제한
- 0 ≤ N ≤ 10^12
- 2 ≤ P, Q ≤ 10^9
힌트
⌊x⌋는 x보다 크지 않은 가장 큰 정수이다.