\(\begin{cases}x \equiv a_1 \pmod{m_1} \\x \equiv a_2 \pmod{m_2} \end{cases}\)
\(\begin{cases}x=a_1+k_1m_1 \\x=a_2+k_2m_2 \end{cases}\)
\(k_1m_1+(-k_2)m_2=a_2-a_1\)
设\(d=\gcd(m_1,m_2), e=a_2-a_1\)
使用扩展欧几里得算法求解 \(x,y\) ，满足 \(xm_1+ym_2=d\)
则有\(x \cdot \frac{e}{d} \cdot m_1+y \cdot \frac{e}{d} \cdot m_2=d \cdot \frac{e}{d}\)
对比可得\(\begin{cases}k_1=x \cdot \frac{e}{d} \\k_2=-y \cdot \frac{e}{d} \end{cases}\)
实际上有多组解\(\begin{cases}k_1=x \cdot \frac{e}{d}+\frac{m_2}{d} \cdot n \\k_2=-y \cdot \frac{e}{d}-\frac{m_1}{d} \cdot n\end{cases} , n\in \mathbb{Z}\)
取 \(k_1\) 的最小整数解，\(\begin{cases}A=a_1+k_1m_1 \\M=lcm(m_1,m_2)=\frac{m_1m_2}{d} \end{cases}\)
合并成了 \(x\equiv A \pmod{M}\)
对于有些题目，中间运算结果会爆long
long。不要偷懒使用__int128，下面是错误示范
，乖乖打龟速乘。（也不要手写__int128） 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
typedef long long LL;
LL a[100005],m[100005];
int n;
LL exgcd(LL a,LL b,LL &x,LL &y) {
if (b==0) {x=1,y=0;return a;}
LL d=exgcd(b,a%b,y,x);y-=(a/b)*x;
return d;
}
inline void excrt() {
LL M=1,A=0;
for (int i=1;i<=n;i++) {
LL x,y,d=exgcd(M,m[i],x,y),mm=m[i]/d;
if ((a[i]-A)%d) {puts("No solution!");return;}
x=(x%mm+mm)%mm;
LL k=(LL)((__int128)(a[i]-A)/d*x%mm+mm)%mm;
LL nM=M*mm;
A=(LL)((A+(__int128)k*M)%nM);
M=nM;
}
printf("%lld",A);
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld %lld",&m[i],&a[i]);
excrt();
return 0;
}