본문 바로가기
알고리즘

피사노 주기 [백준 9471] - python

by 우보틀 2022. 2. 13.

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