풀이
주어지는 나머지 M이 모든 case가 일치한다는 보장이 없다.
매번 새로운 피보나치 수열의 수들에 대해 M으로 나눈 나머지로 이루어진 수열을 구해야한다.
다행히도 문제에서 요구하는 수열에는 Pisano Period라는 규칙성이 존재한다.
즉, 모든 피보나치 수열의 수들에 대해 계산할 필요가 없다.
결국 주기에 따라 수열들의 수는 반복을 하기 때문이다.
우선, 아래의 예제 Pisano Period table을 살펴보자.
피보나치 수열들을 K번째 피보나치수로 나누었을 때 나머지들의 수열이다.
즉, Pisano period의 주기는 나머지가 {0, 1}이 나올때를 기준으로 이루어진다는 것을 알 수 있다.
0만 나오는 경우에는 성립하지 않는다.
나머지가 {0, 1}이 나올때까지 반복해주자.
어차피 입력되는 case마다 M값이 다르고 backtracking없이 매번 table을 다시 구해야해 toggling을 적용했다.
소스코드
출처
9471번: 피사노 주기
첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.
www.acmicpc.net
Pisano period - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Period of the Fibonacci sequence modulo an integer Plot of the first 10,000 Pisano periods. In number theory, the nth Pisano period, written π(n), is the period with which the sequenc
en.wikipedia.org
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 18110] solved.ac [Python] (1) | 2023.06.06 |
|---|---|
| [백준 26530] Shipping [Python] (0) | 2023.06.04 |
| [백준 26531] Simple Sum [Python] (0) | 2023.06.02 |
| [백준 26532] Acres [Python] (0) | 2023.06.02 |
| [백준 26546] Reverse [Python] (0) | 2023.05.31 |