백준 2526 - 싸이클 (파이썬)

https://www.acmicpc.net/problem/2526

풀이

수열 A는 다음과 같이 정의할 수 있다.

1. A_0 = N
2. A_i = A_{i-1} * N mod P

수열을 계속 계산하다 보면, 언젠가 같은 값이 다시 등장해서 반복(싸이클)이 발생한다. 이때 반복되는 구간의 길이를 구하는 문제이다.

1. order 딕셔너리는 각 숫자가 몇 번째에 처음 등장했는지를 저장한다.
2. n = n * N % P는 문제에서 정의된 수열의 다음 항을 계산한다.
3. 만약 n이 이미 order에 있다면
   1. 싸이클이 시작된 시점은 order[n]
   2. 현재 시점은 count
   3. 즉, 싸이클 길이는 count - order[n]

코드

# 백준 2526 - 싸이클
# 분류 : 구현
 
N, P = map(int, input().split())
 
n = N
order = {}
count = 0
 
while True :
    if n not in order :
        order[n] = count
        n = n * N % P
        count += 1
    else :
        print(count - order[n])
        break