Python 이 실현 한 중국 잉여 정리 알고리즘 예시

본 고 는 파 이 썬 이 실현 한 중국의 잉여 정리 알고리즘 을 실례 로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
중국의 잉여 정리(Chinese Remainder Theorem-CRT):손자 정리 라 고도 부 르 는데 수론 중의 한 정리 이다.즉,만약 에 한 사람 이 하나의 수 n 이 여러 개의 정수 에 의 해 제 거 된 나머지 를 알 게 된다 면 이런 제 수 는 두 개의 서로 질 적 인 상황 에서 이 사람 은 이 정수 에 의 해 n 을 곱 하여 얻 은 나머지 를 유일 하 게 확정 할 수 있다.
위 키 피 디 아 에서 위 키 피 디 아:중국의 나머지 정 리 는 숫자 이론의 정리 입 니 다,만약 하나 가 여러 정수 에 의 해 정수의 n 의 부문의 나머지 를 알 고 있다 면,다음 하 나 는 고유 하 게 n 의 분할 의 나머지 를 결정 할 수 있 습 니 다 이러한 정수의 제품 에 의 해,조건 에 따라 divisors 쌍 으로 coprime.
한 수 는 n 이 고,두 번 째 는 1 을 나 누고,세 번 째 는 2 를 나 누고,다섯 번 째 는 4 를 나 누고,여섯 번 째 는 5 를 나 누 었 는데,마침 7 로 나 누 어 이 수 n 을 구 했다.
분석:n 은 2 에서 나머지 1 을 제외 하고 개술 이 최소 1 이 라 고 설명 한 후에 이 조건 이 계속 만족 하기 때문에 더 해 야 할 수 는 반드시 2 의 배수 이다.3 에 의 해 나머지 2,즉(1+2*i)%3=2 를 나 누 었 는데 그 중에서 i 는 정수 이다.이후 이 조건 이 계속 충족 되 기 때문에 더 해 야 할 수 는 반드시 3 의 배수 이 고,또 이전 조건 의 제한 때문에 2 와 3 의 최소 공배수 의 정수 배 이다.한 번 의 유추 로 7 로 나 누 어 진 수 를 찾 을 수 있다.

n=1
while(n%3 != 2):
  n += 2
while(n%5 != 4):
  n += 6
while(n%6 != 5):
  n += 30
while(n%7 != 0):
  n += 30

최종 결 과 는 119.
Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.