백준 피사노 주기

[baekjoon 2749] 피보나치 수 3 (DP, 피사노 주기) (C++)

www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 평범한 피보나치 수를 구하는 문제인 것 같지만 주어지는 수의 범위가 10^18이다. 따라서 저만큼의 크기를 갖는 DP 배열을 생성하는 것은 불가능하기에 다른 방법을 이용해야 한다. 피보나치 수를 일정한 크기의 수로 나눈 나머지는 파사노 주기라고 하는 주기를 갖는다고 한다. 주기를 갖게 되면 N을 구하더라도 N%P(주기)와 같은 값을 갖게 된다. www.acmicpc.net/blog/view/28 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = ..