Informatica Online Judge

  승원이와 피보나치 [1220 / 04C4]

Time Limit(Test case) : 100(ms)
Number of users who solved : 125   Total Tried : 691


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이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]