import sys
input = sys.stdin.readline
def solution(num):
answer = 1
mod1, mod2 = 1, 2
while True:
if mod1 % num == 1 and mod2 % num == 1:
break
answer += 1
mod1, mod2 = mod2, (mod1 + mod2) % num
return answer
def BOJ9471():
P = int(input())
for _ in range(P):
N, M = map(int, input().split())
answer = solution(M)
print(f"{N} {answer}")
BOJ9471()
접근 방법:
1. 여러가지 성질이 문제에 주어져있어 이것들도 고려해야 하나 생각이 들었던 문제이다.
문제에서 요구하는 것은 피사노 주기에 대한 길이 이므로 우선 주기를 직접 구해주기로 하였다.
2. mod1 과 mod2는 첫번째 행과 두번째 행이다. 나누는 값이 2이상 이므로 mod1과 mod2는 항상 1을 가지게 되며 이후에 두개의 값이 동시에 1이 된다면 우리는 피사노 주기의 길이를 알 수 있다.
3. 나머지 연산의 분배법칙에 대해 알아보자
해당 문제에서 피보나치 수열을 직접 구해서 일일히 나머지를 구하는 것은 비효율적이라 판단을 했고 나머지 연산의 분배법칙을 이용하여 피사노 주기의 다음 숫자를 알고자 하였다.
a + b = f(n)
a % m = f(n-2) % m
b % m = f(n-1) % m
f(n-2) + f(n-1) = f(n)
(f(n-2) % m + f(n-1) % m) % m = f(n) % m
위 성질을 이용하여 다음 모듈러 연산에 대한 숫자를 구하였다.
https://www.acmicpc.net/problem/9471
9471번: 피사노 주기
첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.
www.acmicpc.net
728x90
'알고리즘' 카테고리의 다른 글
행렬 곱셈 순서 [백준 11049] -python (0) | 2022.02.15 |
---|---|
Dance Dance Revolution [백준 2342] - python (0) | 2022.02.14 |
피보나치 수 3 [백준 2749] - python (0) | 2022.02.12 |
앱 [백준 7579] - python (0) | 2022.02.11 |
곱셈 [백준 1629] - python (0) | 2022.02.10 |