반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 14: 중국인의 나머지 정리 (Chinese Remainder Theorem) 중국인의 나머지 정리 (Chinese Remainder Theorem, CRT)중국인의 나머지 정리(CRT)는 서로 다른 소수들의 모듈러 시스템에서 주어진 나머지 값을 갖는 수를 찾는 방법입니다. CRT는 정수론과 암호학, 병렬 컴퓨팅 등 여러 분야에서 활용됩니다.중국인의 나머지 정리다음은 중국인의 나머지 정리의 기본 공식입니다:주어진 서로 다른 정수 (n_1, n_2, \ldots, n_k)가 서로소(즉, (\gcd(n_i, n_j) = 1), (i \ne j))일 때, 다음과 같은 동시 합동식 시스템을 만족하는 유일한 정수 (x)가 존재합니다: [\begin{cases}x \equiv a_1 \pmod{n_1} \x \equiv a_2 \pmod{n_2} \\vdots \x \equiv a_k \pm.. 2024. 8. 1. 이전 1 다음 반응형
