BOJ 17840 피보나치 음악
알고리즘 문제풀이/BOJ
2020. 1. 9. 03:37
난이도 : Solved.ac 기준 플래티넘 5 출처 : UNIST Programming Contest UNI-CODE 2018 1. 문제 설명 피보나치 수열 $f_i$ 에 대하여, $f_i \mod m$ 들을 쭉 숫자로 이어서 썼다고 하자. 예를 들어, $m = 11$ 이면 1, 1, 2, 3, 5, 8, 2 (13), 10 (21), 1 (34) 이므로 1123582101 이 된다. 이처럼 쭉 쓴 다음 전체를 문자열로 간주하고, $n$ 번째를 빠르게 찾는 문제. 2. 풀이 $n$ 이 $10^{15}$ 정도로 매우 크고, 이러한 쿼리에 10만 번 답해야 하므로 $n$에 대해 매우 빠르게 답해야 한다. Pisano Period 에 의하면, 피보나치 수열의 $\mod m$ 값은 임의의 $m$ 에 대해서 어떤..