CRT&EXCRT（中国剩余定理和扩展中国剩余定理）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
稍微难一点，其实也挺简单。
CRT:
用途：
给定一个同余方程组，保证所有 \(m\) 两两互质:
用于求其解。
具体方法：
自我感觉叫方法好一点，建议理解记忆，公式见下。
首先我们先找一组数 \(n\) ,使得：
因为：如果 \(a \bmod b = t\) 那么 \((a+k\times b) \bmod b = t\) （比较显然
所以：
如果 \(m_1 \mid n_2\) 那么 \((n_1 + n_2) \bmod m_1 = a_1\)
如果 \(m_2 \mid n_1\) 那么 \((n_1 + n_2) \bmod m_2 = a_2\)
也就是说，要想使
只需要
同理，我们设 \(sum=\sum\limits_{i=1}^nn_i,M=\prod\limits_{i=1}^nm_i\) 要想使：
只需要
因为所有 \(m\) 两两互质，所以只需要
接下来考虑怎么求 \(n_i\)
我们设 \(n_i=M\div m_i \times t_i\)
于是我们只需求一个 \(t_i\) ，使其满足
因为 \(M\div m_i\) 是个常数，所以直接用 \(exgcd\)求解即可。
当然也可以先用乘法逆元算 \(M\div m_i \times t \equiv 1\pmod{m_i}\) 在乘上 \(a_i\) ，本质相同。
这样我们就可以求出所有 \(n_i\) ，进而求出 \(x=\sum\limits_{i=1}^nn_i\)，如果 \(x\) 要求最小，只需要 \(\bmod M\) 即可。
公式：
设 \(M=\prod\limits_{i=1}^nm_i,M_i=M \div m_i\)
则
例题
CODE（点击查看）
#include<bits/stdc++.h>
using namespace std;
#define llt long long
int n,m[12],a[12];
template<typename T>
inline void read(T &x){
char s=getchar();x=0;bool pd=false;
while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
while('0'<=s&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
if(pd) x=-x;
}
void exgcd(llt a,llt b,llt &x,llt &y){
if(b==0) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
int main(){
read(n);
long long tm=1,ans=0;
for(int i=1;i<=n;i++) read(m[i]),read(a[i]),tm*=m[i];
for(int i=1;i<=n;i++){
long long lm=tm/m[i],x,y;
exgcd(lm,m[i],x,y);
x=(x%m[i]+m[i])%m[i];
ans=(ans+x*a[i]*lm)%tm;
}
printf("%lld",ans%tm);
}
这里推荐一篇博客，讲的很细（我从那里学的，本文也有很多借鉴。
EXCRT
其实和 \(crt\) 没有什么关联，单纯推式子。
我们来看一下同余方程组
这里不保证 \(m\) 互质
首先看第一二个式子：
变形得到：
整理：
运用 \(exgcd\) 解得 \(k_1\) 的一组解：
将上式带入 \(x = a_1 + m_1k_1\) 得：
变形得到：
于是我们就成功将两个同余方程化简成了一个。
同理化简下去直到一个，求解即可。
例题
CODE（点击查看）
#include<bits/stdc++.h>
using namespace std;
#define llt long long
__int128 n,na=0,nm=1;
template<typename T>
inline void read(T &x){
char s=getchar();x=0;bool pd=false;
while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
while('0'<=s&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
if(pd) x=-x;
}
llt gcd(llt a,llt b){return (b==0)?a:gcd(b,a%b);}
llt lcm(llt a,llt b){return a/gcd(a,b)*b;}
void exgcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
if(b==0) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
inline void hebing(llt a,llt m){
llt sa=a-na;
__int128 x,y;
llt gd=gcd(nm,m);
exgcd(nm,m,x,y);
llt lm=m/gd;x*=(sa/gd),y*=(sa/gd);
x=(x%lm+lm)%lm;
na=na+nm*x;
nm=lcm(nm,m);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
read(n);
for(llt a,m,i=1;i<=n;i++) read(m),read(a),hebing(a,m);
__int128 x,y;
exgcd(1,nm,x,y);
x=(x*na%nm+nm)%nm;
long long ans=x;
printf("%lld",ans);
}