[BOJ/PYTHON] 20412. 추첨상 사수 대작전! (Hard)

백준 문제 링크: https://www.acmicpc.net/problem/20412

문제 요약

난수생성기에서 준표가 비밀리에서 설정한 정수 a, c를 출력

핵심 아이디어

X1 = (a × Seed + c) % m

X2 = (a × X1 + c) % m

...

Xn + 1 = (a × Xn + c) % m

 

a × (Seed - X1) 은 X1 - X2와 m으로 나눴을 경우의 나머지가 동일

a × (Seed - X1) ≡ X1 - X2 (mod m)

a × (Seed - X1)(m - 1) ≡ (X1 - X2) × (Seed - X1)(m - 2) (mod m)

a**(m-1) ≡ 1 (mod m) 인 페르마 소정리에 의해

a × 1 ≡ (X1 - X2) × (Seed - X1)**(m - 2) (mod m)

a ≡ (X1 - X2) × (Seed - X1)**(m - 2) (mod m)

 

X1 = (a × Seed + c) % m에서

X1 ≡ a × Seed + c (mod m)

c ≡ X1 - (a × Seed) (mod m)

 

풀이

# gold2-20412. 추첨상 사수 대작전! (Hard)

import sys
input = sys.stdin.readline

m, seed, x1, x2 = map(int, input().split())
square = seed - x1
num = 1 # 곱하는 거니까 0 아닌 1

# (Seed - X1)**(m - 2) 구하는 과정
# bin: 숫자를 이진 문자열로 바꿈. 맨 앞 0b가 고정적으로 붙어있음. 
for i in reversed(bin(m-2)[2:]):
    if i == '1':
        num = (num * square) % m
    square = (square * square) % m
a = ((x1 - x2) * num) % m
c = (x1 - (a * seed)) % m

print(a, c)

실행 시간

메모리 31256KB, 시간 44ms (python3)