由于exCRT完美的平替了CRT的全部功能，故不再详细复习CRT的相关内容.
考虑如下同余方程组，
\[\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\end{cases}
\]
展开得，
\[a_1 + k_1 \times m_1 = a_2 + k_2 \times m_2
\]
\[\Rightarrow k_1 \times m_1 - k_2 \times m_2= a_2 - a_1
\]
该式子左侧类似裴蜀定理， 则存在 \(\lambda_1, \lambda_2\) 满足 \(\lambda_1 \times m_1 + \lambda_2 \times m_2= gcd(m_1, m_2)\)
当 \(gcd(m_1, m_2) \nmid a_2 - a_1\) 时， 方程组无解.
当 \(gcd(m_1, m_2) \mid a_2 - a_1\) 时， 存在 \(k_1 , k_2\) 满足 \(k_1 \times m_1 - k_2 \times m_2= a_2 - a_1\).
则特解 \(x^* = \frac{a_2 - a_1}{gcd(m_1, m_2)} \times \lambda_1 \times m_1\)， 根据CRT的相关内容，得到通解
\[x = \frac{a_2 - a_1}{gcd(m_1, m_2)} \ \lambda_1 \ m_1 + k_1 \cdot lcm(m_1, m_2)
\]
考虑由多个同余方程组成的方程组，上面通解可表达成
\[x \equiv \frac{a_2 - a_1}{gcd(m_1, m_2)} \ \lambda_1 \ m_1 \pmod{lcm(m_1, m_2)}
\]
由此，以此从方程组中选出两个同余方程进行合并，显然不失一般性。
点击查看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 50;
typedef long long lld;
inline int read() {
register int w = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return w * f;
}
int n;
lld a1, a2, m1, m2;
inline lld gcd(register lld a, register lld b) {
return (!b ? a : gcd(b, a % b));
}
inline lld mul(register lld a, register lld b, register lld p) {
lld ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}
inline lld exgcd(register lld a, register lld b, lld &x, lld &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
register lld g = exgcd(b, a % b, x, y);
register lld tmp = x;
x = y;
y = tmp - a / b * y;
return g;
}
int main(){
n = read();
scanf("%lld%lld", &m1, &a1);
for (register int i = 2; i <= n; ++i) {
scanf("%lld%lld", &m2, &a2);
register lld x, y;
register lld g = exgcd(m1, m2, x, y);
register lld t = m2 / g;
x = (x % t + t) % t;
register lld tmp = m1 / g * m2;
a1 = (a1 + mul(mul((a2 - a1) / g, x, tmp), m1, tmp) + tmp) % tmp;
m1 = tmp;
}
printf("%lld\n", a1);
return 0;
}