【数论】CRT 与 ExCRT
题单介绍
## 中国剩余定理及扩展中国剩余定理
欢迎各位持续向我私信好的 CRT 及 ExCRT 的题目/qq
**[中国剩余定理(Chinese Remainder Theorem, CRT)和扩展中国剩余定理(Extension of Chinese Remainder Theorem, ExCRT)学习笔记](https://www.luogu.com.cn/blog/LinearExpectation/CRT-ExCRT)**。
## 一. 求解目标
对于任意两个 $m_i,m_j$ 满足 $\gcd(m_i,m_j)=1$，存在同余方程组：
$$\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\x\equiv a_3\pmod{m_3}\\\cdots\cdots\\x\equiv a_n\pmod{m_n}\\\end{cases}$$
我们希望能够求出它的最小非负整数解 $x_0$。
## 二.求解方法
我们定义几个变量的值。首先存在 $\alpha=\prod\limits_{i=1}^{n}m_i$，也就是令 $\alpha$ 表示所有模数的乘积，接下来如果要表示不包含某一个方程模数 $m_i$ 的乘积，可以表示为 $\dfrac{\alpha}{m_i}$ 记作 $\alpha_i$，对于 $\alpha_i$ 存在于 $\bmod m_i$ 意义下的的逆元，我们可以把它记作 $inv_i$，这时候一定存在 $\alpha_i\times inv_i\equiv 1\pmod m_i$。
此时我们计算序列 $c$ 满足 $c_i=\alpha_i\times inv_i$，之所以 $c_i$ 不为 $1$ 是因为我们在实数域中进行讨论，并没有在 $\bmod m_i$ 意义下进行讨论，因此他并不等于 $1$。特别的，此时存在方程组的唯一合法解 $x_0$ 使得：
$$x_0=\sum\limits_{i=1}^{n}a_ic_i\pmod\alpha$$
对于模板题「曹冲养猪」我们可以用如下代码进行求解：
```cpp
#include<bits/stdc++.h>
#define int long long
int n,a[99],m[99],al[99],mul=1,ans;
int Exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}int d=Exgcd(b,a%b,x,y),t=x;
x=y;
y=t-(a/b)*y;
return d;
}signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&m[i],&a[i]);
mul=mul*m[i];
}for(int i=1;i<=n;i++){
al[i]=mul/m[i];
int x=0,y=0;
Exgcd(al[i],m[i],x,y);
if(x<0)x+=m[i];
ans+=a[i]*al[i]*x;
}printf("%lld\n",ans%mul);
return 0;
}
```
## 正确性证明
为什么这组解是正确的？我们不妨令 $i=1,2,3,\cdots,n$ 进行讨论。当且仅当 $i\neq j$ 的时候，存在 $\alpha_j\equiv 0\pmod{m_i}$，也就是说除了 $\alpha_i$ 以外所有的 $\alpha_j$ 都包含 $m_i$ 这个因数，这是显然的。而我们确定 $c_i$ 的定义之后，同时可以确定的是 $c_i\equiv\alpha_i\times(inv_i\bmod m_i)\equiv 1\pmod{m_i}$，我想这从逆元的角度理解应该是可以接受的，因此代入有：
$$\begin{aligned}x\equiv&\sum\limits_{j=1}^{n}a_jc_j&\pmod{m_i}\\\equiv& a_ic_i&\pmod{m_i}\\\equiv&a_i\times\alpha_i\times(inv_i\bmod m_i)&\pmod {m_i}\\\equiv& a_i&\pmod{m_i}\end{aligned}$$
因此，我们可以确认对于每一个 $i\in\{1,2,3,\cdots,n\}$ 都存在 $x\equiv a_i\pmod{m_i}$，由此我们进一步推出结论，每一组 $\{a_i\}$ 都对应唯一的一组解，换言之我们可以确定数列 $a$ 与其特定解 $x_0$ 存在双射关系（即一一映射）。
## 扩展形式
我们考虑一种情况，如果模数并非两两互质，又应该怎么解决这个问题？实际上，如果我们寄希望于对 CRT 的内容进行修改于扩展，绝对会遭致当头棒喝——CRT 的核心在于求取逆元构造解，而在不互质的情况下这个逆元甚至可能不存在，因此我们只能完全抛弃先前的思想，更进一步地讨论新的方法。
考虑一件事情：我们解寻常方程组的方式是进行合并方程，从而实现化简的需求。在正常的研究当中，我们希望能够从两个方程组之间的合并方法进行归纳，然后我们就可以进一步推广到所有方程。这其中有两个难点，首先在于两个特殊例子的合并法则能否推广至全体（且为什么），另一个在于这样的变化是否是等价的——合并结果是否包含原来的所有解？是否不会多出新的解？这是需要证明的。
那么我们从简单的模式开始。
存在同余方程 $\begin{cases}x=r_1\pmod{m_1}\\x=r_2\pmod{m_2}\end{cases}$，我们跳脱出同余形式将其写作 $x=k_1m_1+r_1=k_2m_2+r_2$。
确认此时对于右边两个式子的未知数有且仅有 $k_1,k_2$，如果我们移项之后就可以得到 $k_1m_1-k_2m_2=r_2-r_1$，也就是说这是一个不定方程，通过裴蜀定理可以判定是否有解，而剩下的工作可以交给 Exgcd 进行求解，这显然是简单的。我们用 $d=\gcd(m_1,m_2)$ 将两边同时约化之后，记 $p=\frac{m}{\gcd(m_1,m_2)}$ 然后求出来一组特解 $\lambda_1p_1+\lambda_2p_2=1$，表示出 $k$ 就可以得到：
$$\begin{cases}k_1=\dfrac{r_2-r_1}{d}\lambda_1\\k_2=-\dfrac{r_2-r_1}{d}\lambda_2\end{cases}$$
我们任取一个 $k$ 代回原式之中就可以得到 $x=\dfrac{r_2-r_1}{d}\lambda_1m_1+r_1$，这是一个可以被求出来的 $x$，但他不一定是我们要求的最小非负整数解，所以我们要通过特解进一步处理一般解的问题。这时候如果能够手写几个例子，就再好不过了；但是鉴于时间关系，我们不如直接给出引理：
当存在 $x'$ 满足上述方程，则其通解为 $x+k\cdot\text{lcm}(m_1,m_2)$，换言之在模 $\text{lcm}(m_1,m_2)$ 的同类剩余系里，存在 $x\equiv x'$。我们需要确认的是再这样的一个剩余系当中存在唯一解，且这个唯一解是合法解。不妨设不存在唯一解，即存在 $\omega_1,\omega_2$ 同时满足这个方程，且 $\omega_1\ge\omega_2$，则方程作差得到：
$$\begin{cases}\Delta\omega\bmod m_1=0\\\Delta\omega\bmod m_2=0\end{cases}$$
因此我们可以确定 $\text{lcm}(m_1,m_2)|(\omega_1-\omega_2)$，但是实际上这两者的差 $\Delta\omega$ 一定是小于 $\text{lcm}(m_1,m_2)$ 的，但是却能被其整除，所以我们可以断定有且仅有 $\Delta\omega=0$ 于是存在 $\omega_1=\omega_2$，那么我们会发现实质上这两个解是等同的，于是在该完全剩余系中存在唯一解。
代码可以实现：
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
int Exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}int d=Exgcd(b,a%b,x,y),t=x;
x=y;
y=t-(a/b)*y;
return d;
}bool flag;
int a1,a2,n1,n2;
void Trivial(){
int d=a2-a1;
int g,x,y;
g=Exgcd(n1,n2,x,y);
if(!(d%g)){
x=((x*d/g)%(n2/g)+(n2/g))%(n2/g);
a1=x*n1 + a1;
n1=(n1*n2)/g;
}else flag=1;
}long long n,as[100001],ns[100001];
int ExCRT(){
a1=as[0];n1=ns[0];
for(int i=1;i<n;i++){
a2=as[i];
n2=ns[i];
Trivial();
if(flag)return -1;
}return a1;
}signed main() {
cin>>n;
flag=false;
for(int i=0;i<n;i++)
cin>>ns[i]>>as[i];
cout<<(long long)ExCRT()<<endl;
return 0;
}
```