-
피보나치 수 3 <백준 2749번 문제>
문제 출처: https://www.acmicpc.net/problem/2749 ※공식※ 피보나치 수를 나눌 수를 K라고 할 때, 이면, 피사노 주기는 2749번 문제의 출력 조건은 “n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력합니다." 인데, 피보나치 수를 나눈 나머지들은 반드시 주기를 가지며, 이를 피사노 주기라고 한다는 사실을 알게 되었다.1 2 위 내용을 참고해 2749번 문제를 풀면서 사용한 정의는 다음과 같습니다. 피보나치 수를 나눌 수를 K라고 할 때, k=10^n 이면, 피사노 주기는 15∗10^n−1이다. 문제에서 106106 으로 나눈 나머지를 구하라고 했으므로 주기는 1,500,000 이 된다는 것을 알 수 있습니다. 따라서 입력의 최대값이 1,000,000,000,0..
Algorithm
2020. 11. 11.
