시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 134 62 44 50.575%

문제

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

  • A[i] = 1; (i<=0)
  • A[i] = A[ [i/P]-X ] + A[ [i/Q]-Y ] (i>=1, i/P또는 i/Q가 정수가 아닐 때는 가우스 기호를 이용한다. [3.4] = 3을 이용한다.

N, P, Q, X, Y가 주어질 때, A[N]을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, P, Q, X, Y가 주어진다. N은 1013보다 작거나 같은 자연수 또는 0이고, P와 Q는 2보다 크거나 같고, 109보다 작거나 같은 자연수이다. X와 Y는 109보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 A[N]을 출력한다.

예제 입력

10000000 2 3 10000000 10000000

예제 출력

2

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013