普通的 CRT 只能处理模数两两互质的情况，而 EXCRT 可以求得任意情况下同余方程组的通解。
思想：把两个同余方程合并成一个，直到剩下一个。
考虑两个同余方程 \(x\equiv p_1\pmod {m_1},x\equiv p_2\pmod {m_2}\)。
则 \(x=p_1+m_1A=p_2+m_2B\)。移项得 \(m_1A-m_2B=p_2-p_1\)。
这是一个经典的二元一次不定方程，用 exgcd 求出一个 \((A,B)\) 的特解，进而可以求出 \(x\) 的一个特解 \(x_0\)。
定理：若 \(\begin{cases}x\equiv p_1\pmod{m_1}\\x\equiv p_2\pmod{m_2}\end{cases}\) 有特解 \(x_0\)，则其通解为 \(x_0+k\cdot lcm(m_1,m_2)\)，\(k\in \mathbb{Z}\)。
证明：首先，\(x_0+k\cdot lcm(m_1,m_2)\) 满足同余方程组是显然的。只需要证明为什么没有其他形式的解。也就是为什么模 \(lcm(m_1,m_2)\) 的完全剩余系里，只有余 \(x_0\) 的才有解。
这个问题等价于证明 \(0\sim lcm(m_1,m_2)-1\) 中只有一个有解。
假设有两个解 \(x_1,x_2\)，有 \(x_1\equiv x_2\pmod {m_1}\) 和 \(x_1\equiv x_2\pmod{m_2}\)，所以 \(lcm(m_1,m_2)\mid (x_1-x_2)\)，而 \(x_1,x_2\) 均在 \([0,lcm(m_1,m_2)-1]\) 中，所以 \(x_1=x_2\)。证毕。
所以这两个同余方程可以合并为 \(x\equiv x_0\pmod {lcm(m_1,m_2)}\)。不断合并，直到只剩下一个 \(x\equiv X\)，\(X\) 即为最小非负整数解。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
inline __int128 read()
{
__int128 x=0,f=1;
char ch;
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(__int128 x)
{
if(x<0)putchar('-'),x=-x;
if(x>=10)write(x/10);
putchar(x%10+'0');
}
int n;
__int128 a[N], b[N];
typedef pair<__int128, __int128> pii;
queue<pii> q;
void exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
if (b == 0) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, x, y);
__int128 x0 = x, y0 = y;
x = y0;
y = x0 - (a / b) * y0;
return ;
}
__int128 gcd(__int128 a, __int128 b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
__int128 lcm(__int128 a, __int128 b) {
return a * b / gcd(a, b);
}
void chk() {
pii f1 = q.front();
q.pop();
pii f2 = q.front();
q.pop();
__int128 p1 = f1.first, m1 = f1.second, p2 = f2.first, m2 = f2.second;
if ((p2 - p1) % gcd(m1, m2) != 0) {
cout << "NIE\n";
exit(0);
}
__int128 g = gcd(m1, m2), A, B;
exgcd(m1 / g, m2 / g, A, B);
__int128 t = p1 + (p2 - p1) / g * A * m1 % lcm(m1, m2);
if (t >= 0)
q.push(make_pair(t, lcm(m1, m2)));
else {
t += lcm(m1, m2);
q.push(make_pair(t, lcm(m1, m2)));
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
b[i] = read();
a[i] = read();
q.push(make_pair(a[i], b[i]));
}
for (int i = 1; i < n; i++)
chk();
write(q.front().first);
return 0;
}