其实 \(EX\) 很简单，和普通几乎一样，先上普通版只是心理缓冲 为什么普通版还没淘汰啊。
作用：
解线性同余方程组。
即：
\[ \begin{cases} x\equiv a_1\quad(mod\;m_1)\x\equiv a_2\quad(mod\;m_2)\\quad \dots\x\equiv a_k\quad(mod\;m_k)\\end{cases} \]
限定： \(m\) 之间两两互质。
方式：
分别解：
\[
\begin{cases}
x\equiv a_1\quad(mod\;m_1)\x\equiv 0\quad(mod\;m_2)\\quad \dots\x\equiv 0\quad(mod\;m_k)\\end{cases}
\begin{cases}
x\equiv 0\quad(mod\;m_1)\x\equiv a_2\quad(mod\;m_2)\\quad \dots\x\equiv 0\quad(mod\;m_k)\\end{cases}
\begin{cases}
x\equiv 0\quad(mod\;m_1)\x\equiv 0\quad(mod\;m_2)\\quad \dots\x\equiv a_k\quad(mod\;m_k)\\end{cases}
\]
解法：
设 \(M=\prod_{i=1}^k m_i\) ，\(M_i=\frac{M}{m_i}\) 。
这样就保证了 \(M_i\) 除了模 \(m_i\) 以外都为 \(0\) 。然后我们要解 $M_it_i\equiv a_i\quad(mod;m_i) $ ，用 \(exgcd\) 解就行辽。 当然我们可以发现，\(t_i\) 是 \(M_i\) 的逆元乘 \(a_i\) ，如果处理过逆元就不用再解方程了。
最终答案是 \(\sum_{i=1}^{k} M_it_i\) 。
注意，为了满足所有的 \(mod\;m\) 成立，统计答案时必须模 \(m\) 的 \(lcm\) ，因为它们互质，所以模 \(M\) 就行辽。
模板题，但是要打快龟速乘（\(O(log^n)\)）。
如果在一些奇怪的地方看到一些奇怪的快光速乘（\(O(1)\)） ,最好不要打，\(int128\) 考试用不了，\(long\ double\) 也非常玄学，会锅。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef int int_;
#define int long long
int n;
int m[20],aa[20],bb[20];
int M=1,ans;
int times(int x,int y,int p){
int ret=0,flag=0;
if(y<0){
y=-y;
flag=1;
}
while(y>0){
if(y&1) ret=((ret+x)%p+p)%p;
x=((x<<1)%p+p)%p;
y>>=1;
}
if(flag) return (((-ret)%p)+p)%p;
else return ((ret%p)+p)%p;
}
void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
}
else{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
int_ main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&aa[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&bb[i]);
M*=bb[i];
}
for(int i=1;i<=n;i++){
m[i]=M/bb[i];
int p,q;
exgcd(m[i],bb[i],p,q);
p=times(p,aa[i],M);
p=((p%M)+M)%M;
ans+=times(m[i],p,M);
ans%=M;
}
printf("%lld",ans);
return 0;
}
普通版 \(CRT\) 其实有点 \(low\) ，看看就行辽，重点在 \(EXCRT\) 。
作用
同上，解线性同余方程组，但是没有 \(m\) 互质的条件。
\[
\begin{cases}x\equiv a_1\quad(mod\;m_1)\\x\equiv a_2\quad(mod\;m_2)\\\quad \dots\\x\equiv a_k\quad(mod\;m_k)\\\end{cases}
\]
这样我们就要一个一个解：
对于一个同余方程，设已经解出其前面的方程的通解 \(ans\) 。那么我们就要解：
\[
\begin{cases}
x\equiv ans\quad(mod\;M)\x\equiv a_i\quad(mod\;m_i)
\end{cases}
\]
其中 \(M\) 是前面方程的 \(m\) 的 \(lcm\)。
方程组可以化成：
\[
m_ip+a_i= Mq+ans\implies m_ip+M(-q)=ans-a_i
\]
之后用 \(exgcd\) 解出 \(p\) 或 \(q\)，那么 \(x=m_ip+a_i\) 或 \(x=Mq+ans\) 。
可以注意到，当 \(m\) 两两互质时 \(\gcd(M,m_i)=1\) 即方程一定有解，而 \(gcd(M,m_i)\) 无法整除 \((ans-a_i)\) 时方程无解。
\(excrt\) 的难点主要在于取模的细节。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef int int_;
#define int long long
int n,ans,M,m[100050],aa[100050],bb[100050];
int times(int x,int y,int p){
int ret=0,flag=0;
if(y<0){
y=-y;
flag=1;
}
while(y>0){
if(y&1) ret=(ret+x)%p;
x=(x<<1)%p;
y>>=1;
}
if(flag) return (((-ret)%p)+p)%p;
else return ((ret%p)+p)%p;
}
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
}
else{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
int_ main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld",&aa[i],&bb[i]);
}
ans=bb[1],M=aa[1];
for(int i=2;i<=n;i++){
int g=gcd(aa[i],M);
if((ans-bb[i])%g != 0){
printf("No Solution");
return 0;
}
int x,y;
exgcd(aa[i],M,x,y);
x=times(x,(ans-bb[i])/g,M/g);//这里是gcd求最小正整数解，要模另一个系数除gcd
M*=aa[i]/g;
ans=(times(aa[i],x,M)+bb[i]+M)%M; //为了保证模意义下成立，要模更新过的lcm
}
printf("%lld",ans);
return 0;
}原文：https://www.cnblogs.com/thornblog/p/11890895.html