Chinese remainder theorem again(中国剩余定理+不互质版+hud17

我知道部分同学最近在看中国剩余定理,就这个定理本身,还是比较简单的:假设m1,m2,…,mk两两互素,则下面同余方程组:x≡a1(mod m1)x≡a2(mod m2)…x≡ak(mod mk)在0<=<m1m2…mk内有唯一解。记Mi=M/mi(1<=i<=k),因为(Mi,mi)=1,故有二个整数pi,qi满足Mipi+miqi=1,如果记ei=Mi/pi,那么会有:ei≡0(mod mj),j!=iei≡1(mod mj),j=i很显然,e1a1+e2a2+…+ekak就是方程组的一个解,这个解加减M的整数倍后就可以得到最小非负整数解。这就是中国剩余定理及其求解过程。现在有一个问题是这样的:一个正整数N除以M1余(M1 – a),除以M2余(M2-a), 除以M3余(M3-a),总之,, 除以MI余(MI-a),其中(a<Mi<100 i=1,2,…I),求满足条件的最小的数。

有多远,走多远,把足迹连成生命线。

Chinese remainder theorem again(中国剩余定理+不互质版+hud17

相关文章:

你感兴趣的文章:

标签云: