# 연립 합동방정식 해 구하기
# crt 함수: 2개의 연립방정식 해 구하기
# crt2 함수: n개의 연립방정식 해 구하기 (손자산경, 계란 실은 트럭)
# '친절한 수론 길라잡이' 연습문제 11.8
# gcd(m, n) = 1을 만족하는 네 개의 수 (b, m, c, n)을 입력하면 0<= x <m*n 범위에서
# x = b (mod m), x = c (mod n)
# 을 만족하는 정수 x를 계산하는 프로그램을 만들어 보시오.
# 예:
# x = 1 (mod 3), x = 2 (mod 5)
# 3 * 5 = 15 미만에서 x의 값을 모두 찾는다.
# x = {1, 4, 7, 10, 13} (mod 3)
# x = {2, 7, 12} (mod 5)
# 첫번째 x값 목록과 두 번째 x값 목록의 교집합을 찾으면 그것이 두 식을 모두 만족하는 x값이다.
# gcd(m, n) = 1이면 m*n 이하에 그 해는 하나만 있다.
def crt(b, m, c, n): # Chinese Remainder Theorem
# 예시)
# x = 1 (mod 3)
# x = 2 (mod 5)
mn = m * n
b_lst = []
for i in range(b, mn, m):
b_lst.append(i)
c_lst = []
for i in range(c, mn, n):
c_lst.append(i)
return set(b_lst) & set(c_lst)
print(crt(1, 3, 2, 5))
print(crt(3, 7, 5, 9))
print(crt(3, 37, 1, 87))
#=============================================================
# 정해지지 않은 개수의 인자들을 받아 중국인 나머지 정리의 해를 구한다.
# 예: 5, 7, 2, 12, 8, 13
def crt2(*args): # 가변인자를 받는다
length = len(args) # 인자의 개수를 구한다 # 6
if length % 2 != 0:
print("인자의 개수는 짝수여야 합니다.")
return
r = []
m = []
multi_mn = 1 # 각 m을 모두 곱한 값이다. 이 값 이내에 해가 하나 있다.
for i in range(0, length, 2):
r.append(args[i])
m.append(args[i+1])
multi_mn *= args[i+1]
# mul_mn (= m1*m2*m3...)을 먼저 구해야 각 식의 해를 구할 수 있음. 위에서 구한 이유
answers = [] # 각 방정식마다 해를 구해 모은 집합
for i in range(len(r)):
answer = [i for i in range(r[i], multi_mn, m[i])] # 첫번째 방정식의 해 집합
answers.append(answer)
solution = set(answers[0].copy())
# 교집합을 누적으로 구해야 해서, 해집합 1을 0번째 교집합으로 둔다.
for i in range(len(answers)-1): # 교집합을 구한다. 해 집합이 2개일 경우, 그 교집합 계산은 1번
solution = solution & set(answers[i+1])
return sorted(solution)
print()
# 연습문제 11.5
print(crt2(1, 3, 2, 5))
print(crt2(3, 7, 5, 9))
print(crt2(3, 37, 1, 87))
print(crt2(5, 7, 2, 12, 8, 13))
# 연습문제 11.6 <손자산경> 풀이
# x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7)
print()
print(crt2(2, 3, 3, 5, 2, 7))
# 연습문제 11.7 계란을 실은 트럭
# x = 1 (mod 2), x = 1 (mod 3), x = 1 (mod 4), x = 1 (mod 5), x = 1 (mod 6), x = 0 (mod 7)
print(crt2(1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 0, 7))결과:
{7}
{59}
{262}
[7]
[59]
[262]
[866]
[23]
[301, 721, 1141, 1561, 1981, 2401, 2821, 3241, 3661, 4081, 4501, 4921]