아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

피보나치 수의 나머지

면접 대비

시간 제한1초메모리 제한128 MB

요약
1, 1로 시작하는 피보나치 수열에서 P번째 수를 Q로 나눈 나머지를 테스트 케이스마다 Case #x: M 형식으로 출력합니다.
난이도

쉬움10점 중 2점

유형
수학, 시뮬레이션
정답자
아직 제출이 없습니다

문제

피보나치 수열은 다음과 같이 시작한다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

첫째 항과 둘째 항은 1이고, 셋째 항부터는 바로 앞 두 항의 합이다. 즉 F1=F2=1F_1 = F_2 = 1이고, i≥3i \ge 3이면 Fi=Fi−1+Fi−2F_i = F_{i-1} + F_{i-2}이다.

정수 PP와 QQ가 주어질 때 FPF_P를 QQ로 나눈 나머지를 구한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다.

이어지는 TT개의 줄에 테스트 케이스마다 정수 PP와 QQ가 공백으로 구분되어 주어진다.

출력

테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다.

xx는 1부터 시작하는 테스트 케이스 번호이고, MM은 FPF_P를 QQ로 나눈 나머지이다.

제한

  • 1≤P≤100001 \le P \le 10000
  • 1≤Q≤20000000001 \le Q \le 2000000000

예제1

  1. 예제 1

    입력
    10
5 10
6 25
10 21
32 43
100 100
50 50
25 25
45 67
109 32
128 128
    예상 출력
    Case #1: 5
Case #2: 8
Case #3: 13
Case #4: 15
Case #5: 75
Case #6: 25
Case #7: 0
Case #8: 19
Case #9: 9
Case #10: 69