풀이
Pisano Period를 이용해 풀이했다.
위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다.
이러한 주기를 Pisano Period라고 부른다.
Pisano Period는 다음과 같이 이용된다.
- n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다.
Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다.
- MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다.
소스코드
#include <stdio.h>
#define MOD 1000000
#define P 1500000
int dp[P]={0,1};
int main(){
long long n;
scanf("%lld", &n);
for (int i = 2; i < P; i++)
dp[i] = (dp[i-1] + dp[i-2]) %MOD;
printf("%d", dp[n%P]);
}
출처 및 참고자료
2749번: 피보나치 수 3
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
Pisano period - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Period of the Fibonacci sequence modulo an integer Plot of the first 10,000 Pisano periods. In number theory, the nth Pisano period, written π(n), is the period with which the sequenc
en.wikipedia.org
[백준 9471] 피사노 주기 [C]
풀이 Pisano Period는 다음과 같다. 즉, 모든 주기의 시작점인 {0, 1}이 나올때 까지 피보나치 수를 입력된 M으로 나누며, 횟수를 세면 된다. 소스코드 #include int main(){ int P, N, M; scanf("%d", &P); whi..
kyr-db.tistory.com
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 1934] 최소공배수 [C] (0) | 2021.08.03 |
---|---|
[백준 1620] 나는야 포켓몬 마스터 이다솜 [C/C++] (0) | 2021.08.02 |
[백준 14731] 謎紛芥索紀 (Large) [C] (0) | 2021.08.02 |
[백준 14730] 謎紛芥索紀 (Small) [C] (0) | 2021.08.01 |
[백준 13171] A [C] (0) | 2021.08.01 |