피보나치 > 문제은행

본문 바로가기


알고리즘 분할정복

1053 : 피보나치

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 248 회    시도횟수: 682 회   



피보나치 정수 수열에서 F0 = 0, F1 = 1 이다. 그리고 모든 n ≥ 2 에 대하여 다음과 같이 정의 된다 Fn = Fn-1 + Fn-2 .

 
예를 들어 피보나치수열의 처음 몇 항들은 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … 이다.
 
피보나치수열의 다른 공식은 다음과 같다.
 
7ce7f2eba5731c8babe39036322897a0_1449815 
 

주어진 정수 n에 대하여 당신이 할 일은 피보나치수열 Fn의 마지막 4자리수를 구하는 것이다.


입력은 여러 개의 test case를 포함할 수 있다.
각 test case는 한 줄에 n (0 ≤ n ≤ 1,000,000,000)을 포함한다.
입력의 끝은 −1을 포함한 한 줄로 주어진다.


각 test case에 대해 ,Fn의 마지막 4자리수를 출력한다. (이를테면 Fn을 10,000 으로 나눈 나머지를 출력한다).
만약 마지막 네 자리가 모두 0 이라면 '0' 을 출력한다. 그렇지 않다면, 모든 leading zero는 제거한다.

[Copy]
0
9
999999999
1000000000
-1
[Copy]
0
34
626
6875


행렬 곱셈은 결합연산이 가능하며 두 2행 2열 행렬의 곱은 아래와 같다:

또 어떤 2행 2열 행렬에 대해서도 행렬의 0승은 단위행렬과 같다.

주 : 단위행렬 - A * B = A 일 경우 B를 단위행렬이라고 한다.



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.