中國(guó)剩余定理

問題

求解同余方程組

其中$m_1,m_2,m_3...m_k$為兩兩互質(zhì)的整數(shù)
求x的最小非負(fù)整數(shù)解

定理
令$M={\prod }_{i=1}^k{m}_i$，即M是所有 $m_i$的最小公倍數(shù)
$t_i$為同余方程 $M_t/m_i\equiv 1(mod{m}_i)$的最小非負(fù)整數(shù)解
則有一個(gè)解為$x={\sum }_{i=1}^k{a}_i\frac{M}{m_i}{t}_i$
通解為$x+i?M(i\in Z)$
特別的，最小非負(fù)整數(shù)解為(x%M+M)%M
證明

代碼實(shí)現(xiàn)
同余式的求解可以用擴(kuò)展歐幾里得

void exgcd(int a,int b,int &x,int &y) {if(b==0){ x=1; y=0; return;}exgcd(b,a%b,x,y);int tp=x;x=y; y=tp-a/b*y; }int china() {int ans=0,lcm=1,x,y;for(int i=1;i<=k;++i) lcm*=b[i];for(int i=1;i<=k;++i){int tp=lcm/b[i];exgcd(tp,b[i],x,y);x=(x%b[i]+b[i])%b[i];//x要為最小非負(fù)整數(shù)解ans=(ans+tp*x*a[i])%lcm;}return (ans+lcm)%lcm; }

擴(kuò)展中國(guó)剩余定理

求解同余方程組

其中$m_1,m_2,m_3...m_k$不一定為兩兩互質(zhì)的整數(shù)
求x的最小非負(fù)整數(shù)解
求解：
求解
假設(shè)已經(jīng)求出前k-1個(gè)方程組成的同余方程組的一個(gè)解為x
且有$M={\prod }_{i?1}^{k?1}{m}_i$
則前k-1個(gè)方程的方程組通解為x+i?M(i∈Z)x+i*M(i\in Z)x+i?M(i∈Z)

那么對(duì)于加入第k個(gè)方程后的方程組
我們就是要求一個(gè)正整數(shù)t，使得
$x+t?M\equiv a_k(mod{m}_k)$

轉(zhuǎn)化一下上述式子得
$t?M\equiv a_k?x(mod{m}_k)$

對(duì)于這個(gè)式子我們已經(jīng)可以通過(guò)擴(kuò)展歐幾里得求解t
若該同余式無(wú)解，則整個(gè)方程組無(wú)解
若有，則前k個(gè)同余式組成的方程組的一個(gè)解解為$x_k=x+t?M$

所以整個(gè)算法的思路就是求解k次擴(kuò)展歐幾里得

#include<iostream> using namespace std; #define LL long long LL mi[1100],ai[1100];//mi為要模的數(shù),ai為余數(shù)。 LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a%b); } void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {if(!b){d = a, x = 1, y = 0;}else{exgcd(b, a%b, d, y, x);y -= x * (a / b);} } LL CRT(LL l, LL r, LL *mi, LL *ai) {LL lcm = 1;for(LL i = l; i <= r; i++)lcm = lcm / gcd(lcm, mi[i]) * mi[i];for(LL i = l+1; i <= r; i++){LL A = mi[l], B = mi[i], d, x, y, c = ai[i] - ai[l];exgcd(A, B, d, x, y);if(c % d)return -1;LL mod = mi[i] / d;LL k = ((x * c / d) % mod + mod) % mod;ai[l] = mi[l] * k + ai[l];mi[l] = mi[l] * mi[i] / d;}/*if(ai[l] == 0)return lcm;*/ //保證結(jié)果為正整數(shù)return ai[l]; } int main() {LL t,n,i,aa;while(cin>>n>>aa){if(n==0) break; for(i=1; i<=n; i++){cin>>mi[i];ai[i]=mi[i]-aa;}cout<<CRT(1ll,n,mi,ai)<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数学--数论--中国剩余定理+扩展中国剩余定理（孙子定理）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。