西安网站建设专业公司,做网站需要几个岗位,网站开发的招标参数,微信小程序网站建设方案中国剩余定理又称孙子定理#xff0c;是数论中一个重要定理。最早可见于我国的数学著作《孙子算经》卷下“物不知数”问题#xff0c;原文如下#xff1a;
有物不知其数#xff0c;三三数之剩二#xff0c;五五数之剩三#xff0c;七七数之剩二。问物几何#xff1f;即…中国剩余定理又称孙子定理是数论中一个重要定理。最早可见于我国的数学著作《孙子算经》卷下“物不知数”问题原文如下
有物不知其数三三数之剩二五五数之剩三七七数之剩二。问物几何即一个整数除以三余二除以五余三除以七余二求这个整数。
把这题转化成现代数学问题
求一个数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_totalfor 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结果为
