首页 > 其他 > 详细

中国剩余定理详解

时间:2019-08-20 23:10:30      阅读:100      评论:0      收藏:0      [点我收藏+]

START

中国剩余定理用于求解线性同余方程组:

a = a1 (mod n1)

a = a2 (mod n2)

a = a3 (mod n3)

........

a = ai (mod ni)

任意ni和nj(i != j)互质,问a的值。

我们可以把a写成a=Σai*ci,(ci待求),这个式子要满足两个条件:

1.任意i!=j时ai*ci%nj=0

2.满足ai*ci%ni=ai。

只要满足了这两个条件的a就是我们要求的a。

如何求ci?:

因为正整数n1,n2......ni都互质,那么任意 i != j 都有gcd(ni,nj)=1。

设mi=(n)/ni。其中n=n1*n2*n3*.......*ni。

于是有gcd(ni,mi)=1。

根据扩欧的性质我们知道,存在mi‘,ni‘使得mi*(mi‘)+ni*(ni‘)=1。

在模ni的条件下就是:mi*(mi‘) = 1 (mod ni)。------①

显然,令ci=mi*(mi‘),这样的ci是满足条件2的(将①左右同时×ai)

又因为mi包含有nj(i!=j) ,则mi*(mi‘)%nj =0(i!=j),左右同时×ai得到ai*mi*(mi‘)=0 (mod nj)所以条件1也成立

现在求ci就是求mi*mi‘的问题。

mi和mi‘都很好求。

mi=n/ni。

mi‘直接用扩欧来求,实际上在求的过程我们发现mi‘就是mi的逆元,用扩欧求mi相对ni的逆元就是我上面介绍的原理(如果ni和mi互质的话还可以用费马小定理求解逆元)

求出ai*mi*mi‘后累加即可得到a。

到此,中国剩余定理就讲完了。

模板代码网上很多,这里就不贴了。

END

 

中国剩余定理详解

原文:https://www.cnblogs.com/cautx/p/11386001.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!