피보나치 > 문제은행 : 정보올림피아드&알고리즘



1053 : 피보나치

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
585 회   
시도횟수
1194 회   

문제

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

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

주어진 정수 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는 제거한다.


입력 예

0
9
999999999
1000000000
-1

출력 예

0
34
626
6875

Hint!

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

 

 

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

 

 

 

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



분할정복

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP