백준 6064번의 문제를 단순히 풀려고 하면 시간 초과가 생긴다.
이를 해결하기 위해서 공부해야 하는 것이 아래의 "중국인의 나머지 정리"이다.
수론과 환론에서 중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다.
(출처: 위키백과)
https://ko.wikipedia.org/wiki/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%A0%95%EB%A6%AC
중국인의 나머지 정리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 청나라 때 출판된 《손자산경》 사본. 중국인의 나머지 정리는 《손자산경》에서 최초로 언급되었다. 수론과 환론에서 중국인의 나머지 정리(中國人-定理, 영
ko.wikipedia.org
아래 링크는 이해하기 쉽게 풀어놓은 블로그 글이다.
중국인의 나머지 정리 - 이해하기 쉬운 설명
중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때
blog.joonas.io
중국인의 나머지 정리를 이해하려면 확장 유클리드 알고리즘도 알아보면 좋다.
https://thfist-1071.tistory.com/251
Extended Euclidean Algorithm 확장된 유클리드 알고리즘
https://thfist-1071.tistory.com/entry/C-%EC%96%B8%EC%96%B4-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%A6%9D%EB%AA%85-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A1%9C-%EA%B5%AC [C 언어] 유클리드 호제법 증명과 재귀함수
thfist-1071.tistory.com
'Algorithm' 카테고리의 다른 글
| [알고리즘] 유니온 파인드 (0) | 2025.04.11 |
|---|---|
| [Python] 힙 라이브러리 (heapq) (0) | 2025.04.07 |
| [CS] 메모이제이션(memoization) (0) | 2024.11.29 |
| 파라메트릭 서치(Parametric Search)와 이진탐색(Binary Search) (0) | 2024.10.14 |
| 이진 탐색 (이분 탐색) (Binary Search) (0) | 2024.10.08 |