首页 > 代码库 > 【数论】中国剩余定理
【数论】中国剩余定理
问题:给定a1a2...an, 和m1,m2...mn,mi之间两两互质,求一个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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。