[Algorithm🧬] 백준 2526 : 싸이클

문제

문제에 나온 연산을 해서 나온 어떤 수가 나오는 순간 사이클이 생기는 것 (뒤는 반복될 것이므로)
현재 index - 해당 수가 전번에 나온 index 해서 몇 개가 반복되는지 알 수 있다.

import sys

readl = sys.stdin.readline

n, p = map(int, readl().split())

sol = 0
arr = []
# used = [0] * (1000 + 1) # n, p 크기에 따라 1001 로 결정.

temp = n
i = 0
while True:
    temp = temp * n % p
    # 간단한 문제니까 in arr 로 할 수 있었지만, 메모리 제한이 있다면
    # if used[temp] > 0:
    #    sol = i - used[temp]
    #    break
    if temp in arr:
        sol = i - arr.index(temp)
        break
    
    # used[temp] = i # 순서 저장.
    arr.append(temp)
    i += 1


print(sol)

만약 메모리 제한이 있다면...

import sys

readl = sys.stdin.readline

n, p = map(int, readl().split())

sol = 0
used = [0] * (1000 + 1) # n, p 크기에 따라 1001 로 결정.

temp = n
i = 0
while True:
    temp = temp * n % p
    # 간단한 문제니까 in arr 로 할 수 있었지만, 메모리 제한이 있다면
    if used[temp] > 0:
       sol = i - used[temp]
       break
    
    used[temp] = i # 순서 저장.
    i += 1


print(sol)