무한 수열 2
시간 제한10초메모리 제한512 MB
각 항이 두 개의 내림 나눗셈으로 정의된 재귀 수열 A_N을 계산하는 문제로, 서로 다른 인자 수가 제한됨을 이용한 메모이제이션 재귀가 필요합니다.
문제
수열 A는 모든 정수 i에 대해 다음과 같이 정의된다.
- i ≤ 0이면 A_i = 1이다.
- i ≥ 1이면 A_i = A_{⌊i / P⌋ - X} + A_{⌊i / Q⌋ - Y}이다.
정수 N, P, Q, X, Y가 주어질 때 A_N을 구하시오.
입력
첫째 줄에 정수 N, P, Q, X, Y가 공백으로 구분되어 주어진다.
출력
A_N의 값을 한 줄에 출력한다.
제한
- 0 ≤ N ≤ 10^13
- 2 ≤ P, Q ≤ 10^9
- 0 ≤ X, Y ≤ 10^9
힌트
⌊x⌋는 x보다 크지 않은 가장 큰 정수를 뜻한다.