孙子剩余定理代码C语言实现?
发布网友
发布时间：2022-05-01 18:28
共3个回答
热心网友
时间：2022-06-21 05:38
热心网友
时间：2022-06-21 05:39
书里面给了计算过程及答案：70*2 + 21*3 + 15*2 -105*2 = 23。
它的计算思路如下：
70是能被5或7整除的数字，但是除以3正好余1。
21是能被3或7整除的数字，但是除以5正好余1。
15是能被3或5整除的数字，但是除以7正好余1。
所以若有数N = 70 * N1 + 21 * N2 + 15 * N3(其中N,N1,N2,N3为正整数)，则整数N是符合题目要求的结果(mod3为N1，mod5为N2， mod7为N3)。
我们把N1赋值2，N2赋值3，N3赋值2。
则: N = 70*2 + 21*3 + 15*2 = 233。
但是3，5，7的最小公倍数为105。
所以N + 105*M均为正解。
因此为了求得最小正整数解，我们需要用(N mod 105)也就是23了。
中国剩余定理(西方数学史中的叫法)，就是上一题目的一般情况。
设m1,m2...mk是两两互素的正整数，即: *(mi, mj) = 1 (其中 i != j, i, j >= 1且 <=k).
则同余方程组:
x ≡ a1(mod m1)
x ≡ a2(mod m2)
... ...
x ≡ ak(mod mk)
存在唯一[m1,m2...mk]使方程成立.
解法同物不知数是一致的.我们可以稍微模仿一下.
唯一的难题就是如何把上面70, 15, 21的求法,对应到一般情况来.
假设: N1, N2, ... ,Nk.就是对应的权值, 满足如下条件:
N1 能够被 m2, m3..., mk整除,但是除以m1正好余1.
N2 能够被 m1, m3..., mk整除,但是除以m2正好余1.
... ...
Nk能够被m1, m2,...,mk-1整除,但是除以mk正好余1.
N1->Nk如果求出来了,那么假设:
x1 = N1*a1 + N2*a2 + ... + Nk*ak就是我们要求的x一个解, 同物不知数一样,我们把x1 mod (m1*m2*...*mk)的结果
就是x的最小整数解,若为负数,则再加上一个m1*m2*...*mk.因为加减整数倍个m1*m2*...*mk所得结果都是x的解.
所以问题只剩下一个,就是求N1, N2,...,Nk.
怎么求呢?我需要先化简一番:
设m = m1*m2*...*mk, L, J为任意整数.
因为Ni能被m1, m2,...,mi-1, mi+1,...,mk整除(其中i+1<k)
因此: Ni = m/mi *L
又因为Ni除以mi余1
因此: Ni = mi*J + 1
即: mi*J + 1 = m/mi *L ==> (-mi)*J + m/mi*L = 1
而m1-->mk这些数都是互质数,所以(-mi) 同 m/mi也是互质数.即:
*(mi, m/mi) = 1也就是说:
(m/mi)*L + (-mi)*J = *(m/mi, -mi)==>其中-mi和m/mi都是已知的,J和L未知
这就是经典扩展欧几里德定理的原型(由定理知J和L是唯一的, 因此,N1-->Nk有唯一解).
按照扩展欧几里德定理求解即可.
扩展欧几里德定理：
a和b都是不全为0的正整数，则：
a*x + b*y = *(a, b)
存在唯一的x, y使得上面等式成立。
(当然，容易得知，如果，a和b中有负数，那么也是成立的。)
本题中，m/mi相当于a, -mi相当于b, L相当于x, J相当于y。求出L, J就能求出Ni。
此时Ni求解完毕.
我们要求的x的最小整数解也就呼之欲出了.
————————————————
版权声明：本文为CSDN博主「hard_man」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/hard_man/article/details/7732795
热心网友
时间：2022-06-21 05:39
