[python3] 백준 23062번 - 백남이의 여행 준비의 준비

문제

중국인의 나머지 정리(CRT)를 알고 있는 사람이라면 바로 해당 정리를 이용해서 문제를 풀어야겠다는걸 알 수 있다.

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)

CRT는 주어진 법들이 서로소 관계일때만 적용되므로, 일반적인 CRT와는 약간 다르게 바꿔서 함수를 짜야 한다.

풀이

import sys
input = sys.stdin.readline

def ext_euc(a, b):
    if b==0: return a, 1, 0
    g, x, y = ext_euc(b, a%b)
    return g, y, x-(a//b)*y

def solve(a1, m1, a2, m2):
    g, k1, k2 = ext_euc(m1, m2)
    q, r = divmod(a2-a1, g)
    if r!=0: return -1,-1
    l = m1*m2//g
    return (k1*q*m1+a1)%l, l

for _ in range(int(input())):
    A, B, C, a, b, c = map(int, input().split())
    ab, AB = solve(a, A, b, B)
    if ab<0: print(-1); continue
    print(solve(ab, AB, c, C)[0])

내 풀이 코드가 엄청 더러워서 푸신 분들 중에 깔끔한 풀이가 있어 그 풀이를 참고해서 재작성하였다.