python实现中国剩余定理
中国剩余定理又称孙子定理，是数论中一个重要定理。最早可见于我国的数学著作《孙子算经》卷下“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。
把这题转化成现代数学问题：
求一个数x，该数除以3余2，除以5余3，除以7余2
把以上问题转化为一般方程的形式
根据中国剩余定理解如下
其中
python代码实现
n = int(input())
b = list(map(int, input().split())) # 余数
m = list(map(int, input().split())) # 模数
M = [0] * n
m_total = 1
x = 0 # 解，初始化为0
for i in range(n):
m_total *= m[i] # 计算m_total
for i in range(n):
M[i] = m_total // m[i] # 计算M[i]
for i in range(n):
x += b[i] * M[i] * pow(M[i], -1, m[i]) # pow(M[i], -1, m[i])表示M[i]模m[i]的逆元
print(x % m_total) # 该解有无数个，取一个模m_total的最小正整数解第一行输入有几个方程
第二行输入每个方程的余数
第三行输入每个方程的模数
如一开始《孙子算经》的那题输入
3
2 3 2
3 5 7
结果为
