首页 > 其他 > 详细

【数论】中国剩余定理

时间:2014-06-26 13:23:31      阅读:391      评论:0      收藏:0      [点我收藏+]

问题:给定a1a2...an, 和m1,m2...mnmi之间两两互质,求一个x,使得x/ai=mi

构造方法:

先求出M=ni=1mi, 对于每个mi,求出M / mi, 然后和mi利用拓展欧几里得算法求出M/mi?p+mi?q=1时的值,取ni=1(p?ai?M/mi)就是答案。

证明:

证明参考了wiki
由于mi之间两两互质,所以gcd(mi,mj)=1,gcd(mi,Mi)=1, 求出数论倒数ti使得Mi?ti%mi=1,这就是上面利用扩展欧几里得算法求出的p值,ai?p?M%mi=ai, 又由于M中包含了其他所有的mj, 所以ai?p?M%mj=0, 因此ni=1(p?ai?M/mi)%mi=ai得证

代码:

for (int i = 0; i < 3; i++) {
    int x, y, w = M / m[i];
    gcd(m[i], w, x, y);
    ans = (ans + p[i] % m[i] * w * y) % M;
}


【数论】中国剩余定理,布布扣,bubuko.com

【数论】中国剩余定理

原文:http://blog.csdn.net/accelerator_/article/details/34472715

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