승원이와 피보나치 [1220 / 04C4]
Time Limit(Test case) : 100(ms)Number of users who solved : 171 Total Tried : 853
The Champion of this Problem (C++) : gs18031 - 0ms / 107byte
My Best Submission (C++) : N/A
[koistudy.net (32nd 구재현)]
Background
sutekine 선생님은 오늘도 koistudy.net의 치팅 코드를 일일히 제거하느라 바쁘시다.특히 오늘은 무슨 날인지 엄청난 양의 치팅 코드가 제출되어서, 선생님은 결국 알고리즘 수업을 포기하시고 다음 문제를 다 계산하면 교무실에 오라고 말씀하신 후, 교실을 나가셨다.
* 피보나치 수열은 F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 (n >= 3) 으로 정의되는 수열이다. 임의의 자연수 x,y가 주어졌을 때, Fx + Fx+1 + .. + Fy 를 3으로 나눈 나머지를 구해라. (1 <= x <= y <= 2,000,000,000)
그 때, 천재 박승원은 이 문제를 보자마자 계산한 후 "다 풀었습니다" 를 외쳐 선생님을 놀라게 했다.
과연 승원이는 어떻게 이 문제를 해결했을까?
Input
두 자연수 x,y가 주어진다.[입력값의 정의역]
1 <= x <= y <= 2,000,000,000
[Sub-Task Info]
#1 : 1 <= x <= y <= 10 (40%)
#2 : 추가 제한 조건은 없다. (60%)
Output
Fx + Fx+1 + .. + Fy 를 3으로 나눈 나머지를 구해라.IO Example
입력3 6
출력
0
설명
F = {1,1,2,3,5,8,...} 이므로, (2 + 3 + 5 + 8) 을 3으로 나눈 나머지는 0이다.
Prob Analysis : [Problem Statistics] | [Solution]
