扩展中国剩余定理，是一种解决同余方程组的利器。
我们从一道板子题说起
P4777 【模板】扩展中国剩余定理（EXCRT）
题目要求我们解下面的方程组：
\[\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}
\]
乍一看，貌似没有什么思路。对于方程组的求解，由于约束条件太多，没法直接求出解，考虑化繁为简。
具体的，回想我们解二元一次方程组的思路：
\[\begin{cases} x + y = a_1 \\ x - y = a_2 \end{cases}
\]
两式相加可得 \(2x=a_1+a_2\) ，这样我们便将两个未知数化为了一个未知数，两个方程合并为了一个方程。
这便是一切方程组的求解思路：消元、减少方程数。
回到原方程组， 由于未知数只有一个，消元便不可行，考虑减少方程数。即将一些方程合并在一起，得到一个等价的新方程。
而 \(\text{exCRT}\) ，给出了同余方程组的合并方法，它的核心内容如下：
定理（exCRT）
对方程
\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \end{cases}
\]
设其特解为 \(x_0\) ，则原方程组可合并为
\[x \equiv x_0 \pmod{[m1,m2]}
\]
证明
\[\begin{align} &\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \end{cases} \\ \\ \Leftrightarrow \quad &\begin{cases} x=k_1m_1+a_1 \\ x=k_2m_2+a_2 \end{cases} \\ \\ \Leftrightarrow \quad &m_1k_1-m_2k_2=a_2-a_1 \end{align}
\]
设上面的方程的特解为 \(k_1=k_1',k_2=k_2'\) ，由不定方程的结论，上面方程的通解为：
\[\begin{cases} k_1=k_1'+\frac{m_2}{(m1,m2)}t \\ k_2=k_2'+\frac{m_1}{(m1,m2)}t \end{cases}
\]
（按照不定方程通解定理，上式两个式子中都应是减号，但由于 \(t\) 取遍所有整数，加减号没啥影响，所以全改加号了）
我们还可以用 \(k_1'\) 表示 \(x\) 的特解 \(x_0=m_1k_1'+a_1\) 。
于是，可求出 \(x\) 的通解
\[\begin{align} x&=k_1m_1+a_1 \\ &=a_1+m_1(k_1'+\frac{m_2}{(m1,m2)}t) \\ &= a_1+m_1k_1'+\frac{m_1m_2}{(m_1,m_2)}t \\ &=x_0+[m_1,m_2]t \end{align}
\]
即得原定理，证毕。
有了exCRT，我们只需将方程组两两合并即可求得解。
对于特解的求解，只需要按上面证明步骤把两个方程的方程组化为不定方程，使用exgcd即可解决。
p4777
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e5+10;
int a[N],m[N];
int n,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, y,x);y-=A/B*x;return d;
}
inline int mul(int x, int y, int p){// 使用快速乘而非龟速乘，可以避免a[i+1]-a[i]为负数的情况x%=p; y%=p;int c=(int)((long double)x*y/p);int ans=x*y-c*p;return (ans%p+p)%p;
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1; i<=n; i++) cin>>m[i]>>a[i];for(int i=1; i<n; i++){int A=m[i], B=m[i+1], C=a[i+1]-a[i];int x,y; int d=exgcd(A, B, x,y), t=B/d;x=mul(x,C/d,t); x=(x%t+t)%t;m[i+1]=m[i]/d*m[i+1];a[i+1]=mul(x,m[i],m[i+1])+a[i];}cout<<a[n];return 0;
}