[BOJ 1354] 무한 수열 2

문제 링크 : https://www.acmicpc.net/problem/1354

문제

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

• A_i = 1 (i ≤ 0)
• A_i = A_⌊i/P⌋-X + A_⌊i/Q⌋-Y (i ≥ 1)

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

입력

첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다.

출력

첫째 줄에 A_N을 출력한다.

제한

시간 제한	메모리 제한
10sec	512MB

• 0 ≤ N ≤ 10¹³
• 2 ≤ P, Q ≤ 10⁹
• 0 ≤ X, Y ≤ 10⁹

힌트

⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.

---

풀이

1351번 문제의 강화 버전이다. 수의 범위가 늘어나고, 시간 제한도 2배 증가했다. 사실 크게 어려울 게 없을 거 같아서, 같은 코드를 제출했었다. 하지만 받게 된 채점은 시간 초과였다. $-X, -Y$가 추가되었더니 1차원 연결리스트로 탐색하는 것은 불가능해지는 것 같았다.

어짜피 방법론은 똑같은 걸 쓰면서, 계산된 수에 대해 빠른 탐색이 필요한 것 뿐이어서, 수의 저장 방식을 해시맵으로 변경하였다. 물론 C를 사용하는 입장에서 stl을 사용할 수는 없으니, 저장 방식 자체는 연결리스트를 사용해야한다. 해시 개수는 $1\,000\,003$를 임의로 사용했다.

소스코드

Github Link : Source Code

참고 알고리즘 :