前言

中國剩余定理（也叫孫子定理）并不是很復雜，由于最近用到了，以前學的時候還不寫博客，所以現在補一下

中國剩余定理（CRT）

問題

給出$n$個同余方程
$$\begin{array}{rl}x& \equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{p}_1)\\ x& \equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{p}_2)\\ ??& ??????\\ x& \equiv a_n(\mathrm{m}\mathrm{o}\mathrm{d}{p}_n)\end{array}$$
保證所有的$p$兩兩互質
求最小自然數解$x$

做法

我們令$$P=\prod _{i=1}^n{p}_i$$
容易發現，$x<P$
證明，若現在求出一個$x$滿足條件且$x\ge P$
那么$(x\mathrm{m}\mathrm{o}\mathrm{d}P)$一定也滿足條件且$(x\mathrm{m}\mathrm{o}\mathrm{d}p)<P$
我們考慮對于一個限制$x\equiv a_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$，我們要進行一種操作，使得其它$n?1$個$p$的模意義下值不變，模$p_i$意義下的值從$0$變為$a_i$
考慮如果我們加上的數是$X?\frac{P}{p_i}$形式的，那么我們就可以滿足“其它$n?1$個$p$的模意義下值不變”，由于保證了所有$p$兩兩互質，所以$\frac{P}{p_i}?\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$
設$\frac{P}{p_i}\equiv v_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$
那么只要加上$(a_i{v}_i^{?1}(\mathrm{m}\mathrm{o}\mathrm{d}\frac{P}{p_i}))\frac{P}{p_i}$就可以滿足這條限制
最后求出$x$后再模$P$就好了

例題

竟然有模板題。。。
洛谷P3868 [TJOI2009]猜數字
有個要注意的地方是這里的逆元應用擴展歐幾里得（exGCD）求，另外由于模數過大，需要用到慢速乘（復雜度$\Theta (logn)$），可以用杜教乘優化（復雜度$\Theta (1)$，我的這篇博客里有提到）

代碼

ac代碼（其實也是板子）

#include<cstdio> #include<cctype> #include<algorithm> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } LL EXgcd(const LL a,const LL b,LL &x,LL &y) { if(!b){x=1,y=0;return a; }const LL res=EXgcd(b,a%b,y,x);y-=a/b*x;return res; } inline LL msc(LL a,LL b,LL mod) {LL v=(a*b-(LL)((long double)a/mod*b+1e-8)*mod);return v<0?v+mod:v; } int n,a[11],p[11]; LL CRT() { LL P=1,sum=0; for(rg int i=1;i<=n;i++)P*=p[i];for(rg int i=1;i<=n;i++) {const LL m=P/p[i];LL x,y;EXgcd(p[i],m,x,y);sum=(sum+msc(msc(y,m,P),a[i],P))%P;}return sum; } int main() {read(n);for(rg int i=1;i<=n;i++)read(a[i]);for(rg int i=1;i<=n;i++){read(p[i]);a[i]=(a[i]%p[i]+p[i])%p[i]; }print(CRT());return flush(),0; }

擴展中國剩余定理（exCRT）

問題

給出$n$個同余方程
$$\begin{array}{rl}x& \equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{p}_1)\\ x& \equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{p}_2)\\ ??& ??????\\ x& \equiv a_n(\mathrm{m}\mathrm{o}\mathrm{d}{p}_n)\end{array}$$
求最小自然數解$x$
（與上面的問題的不同在于這里不保證所有的$p$兩兩互質）

做法

考慮我們現在已經符合了前$k?1$個限制了
設$P=lcm(p_1,p_2???p_k?1)$，容易發現，滿足前$k?1$個限制的最小的自然數$x<P$
證明同理，也就是現在答案是$x+tP$形式的
我們要滿足第$k$個限制，其實很方便，就是找到一個$t$滿足
$$x+tP\equiv a_k(\mathrm{m}\mathrm{o}\mathrm{d}{p}_k)$$
移項$$tP\equiv a_k?x(\mathrm{m}\mathrm{o}\mathrm{d}{p}_k)$$
轉化$$tP+q{p}_k\equiv a_k?x$$
然后直接拓展歐幾里得求解
若無解輸出無解
否則直接將答案更新

例題

洛谷P4777 【模板】擴展中國剩余定理（EXCRT）
這道題保證有解，所以不用判無解了，保證了解的范圍，所以容易發現不用高精度

代碼

貼出ac代碼，代碼里有句注釋，是用來判無解的
為了卡常才把它注釋掉的

#include<cstdio> #include<cctype> #include<algorithm> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } LL EXgcd(const LL a,const LL b,LL &x,LL &y) { if(!b){x=1,y=0;return a; }const LL res=EXgcd(b,a%b,y,x);y-=a/b*x;return res; } inline LL msc(LL a,LL b,LL mod) {LL v=(a*b-(LL)((long double)a/mod*b+1e-8)*mod);return v<0?v+mod:v; } LL n,a[100001],p[100001]; LL EXCRT() { LL P=1,sum=0; for(rg int i=1;i<=n;i++) {const LL o=((a[i]-sum)%p[i]+p[i])%p[i];//if(o%gcd(P,p[i])!=0)return -1;const LL xs=o/gcd(P,p[i]);LL x,y;EXgcd(p[i],P,x,y);const LL M=P;P=P/gcd(P,p[i])*p[i];sum=(sum+msc(msc(y,M,P),xs,P))%P;}return sum; }int main() {read(n);for(rg int i=1;i<=n;i++){read(p[i]),read(a[i]);a[i]=(a[i]%p[i]+p[i])%p[i];}print(EXCRT());return flush(),0; }

總結

并不是很難的兩個算法，學起來很方便
后記：感覺exCRT嚴格優于CRT，有沒有大佬指出CRT有什么用啊

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的中国剩余定理（CRT）扩展中国剩余定理(exCRT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。