[BOJ 13729] 1013 피보나치

이 문제 역시 교육적인 문제. 부분 조건을 이용해 전체 조건을 만족시키게 하는 문제이다. 문제에서 주목할 부분은 $F_{n} \bmod{10^{13}} =N$이 되는 $n$이 있냐는 것이다. 다른 말로 하면 $F_{n}\bmod{10}=N\bmod{10}$이고 $F_{n}\bmod{100}=N\bmod{100}$이고 ...를 만족하는 $n$이 있냐는 것이다. 우린 modulo가 $10^{3}$인 곳에서 시작한다. 왜냐면.. 그때부터 피보나치 수열의 피사노 주기가 $10^{n-1}*15$이기 때문이다. 알고리즘의 작동 원리는 간단하다. 법 $10^{3}$에 대해 $i$번째 피보나치 수와 $N$이 합동인 $i$들을 모아놓자. 이론적으로 1500개만 검사하면 되므로 금방 모인다. 그럼 방금 구한 각각의 인덱스들에 대하여 $10^{3}$의 피사노 주기인 $15*10^{2}$을 더하여 검사한다. 즉, $i+15*10^{2}*m(0 \le m \le 9)$인 인덱스를 모두 검사하여 조건에 맞는 인덱스를 추린다. 이런 방식으로 인덱스 집합을 관리하면 마침내 답을 얻어낼 수 있다. 

비슷한 문제로  '[BOJ 17758] Fibonacci' 가 있는데 수 앞의 0처리를 신경써야하는 것이 차이이다.