문제중국인의 나머지 정리(CRT)를 알고 있는 사람이라면 바로 해당 정리를 이용해서 문제를 풀어야겠다는걸 알 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동nivr4y.tistory.comCRT는 주어진 법들이 서로소 관계일때만 적용되므로, 일반적인 CRT와는 약간 다르게 바꿔서 함수를 짜야 한다.풀이import sysinput = sys.stdin.readlinedef ext_euc(a, b): if b==0: return a, 1, 0 g, x, y = ext_euc(b, a..