中国剩余定理CRT
正整数m1,m2,...,mk两两互素，对b1,b2,...,bk的同余式组为
[begin{cases}
x equiv b_1; mod ;m_1\
x equiv b_2; mod ;m_2\
quadquadvdots\
x equiv b_k; mod ;m_k\
end{cases}
]
在mod M
[M = prod_{i = 1}^{k}m_i
]
的情况下有唯一解
[x = (sum_{i=1}^k b_iM_iM'_i);mod;M
]
其中
[M_i = frac{M}{m_i}
]
[M'_i = M_i^{-1};mod;m_i
]
python代码实现：
import gmpy2
def crt(b,m):
#判断是否互素
for i in range(len(m)):
for j in range(i+1,len(m)):
if gmpy2.gcd(m[i],m[j]) != 1:
print("m中含有不是互余的数")
return -1
#乘积
M = 1
for i in range(len(m)):
M *= m[i]
#求M/mi
Mm = []
for i in range(len(m)):
Mm.append(M // m[i])
#求Mm[i]的乘法逆元
Mm_ = []
for i in range(len(m)):
_,a,_ = gmpy2.gcdext(Mm[i],m[i])
Mm_.append(int(a % m[i]))
#求MiM'ibi的累加
y = 0
for i in range(len(m)):
print(Mm[i] * Mm_[i] * b[i])
y += (Mm[i] * Mm_[i] * b[i])
y = y % M
return y
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
