若存在整数 a.b，除以 m 的余数相同，则称 a，b mod m 同余，记为：
a
≡
b
(
m
o
d
m
)
a\equiv b\qquad (mod\ m)
a≡b(mod m)
同余系 & 剩余系
同余系：对区间 [1,m-1], 集合 {a+km} 的所有数 mod m，余数都是 a，称集合为一个 mod m 的同余类，记做：
a
‾
\overline a
a。
剩余系：mod m 的同余类有 m 个：
0
‾
,
1
‾
.
.
.
m
−
1
‾
\overline 0,\overline 1...\overline {m-1}
0,1...m−1 构成 m 的完全剩余系； [1,m] 中与 m 互质的数代表的同余类有：
ϕ
(
m
)
\phi(m)
ϕ(m) 个，构成 m 的简化剩余系。
简化剩余系关于 mod m 乘法封闭： 任取其中 a，b 与 m 互质，则 a*b 也与 m 互质（反证法证明）。
扩展欧几里得
对于任意整数 a，b，存在一对整数 x，y，有：
a
∗
x
+
b
∗
y
=
gcd
(
a
,
b
)
a*x+b*y = \gcd(a,b)
a∗x+b∗y=gcd(a,b)
证明
若 b = 0，则当：
x
=
1
,
y
=
0
x = 1,y = 0
x=1,y=0 公式成立。
若 b>0, 根据欧几里得算法：
gcd
(
a
,
b
)
=
gcd
(
b
,
a
m
o
d
b
)
\gcd(a,b) = \gcd(b,a\ mod\ b)
gcd(a,b)=gcd(b,a mod b) 此时不妨假设存在：
x
0
,
y
0
x_0,y_0
x0,y0 使得
b
∗
x
0
+
(
a
m
o
d
b
)
∗
y
0
=
gcd
(
b
,
a
m
o
d
b
)
b*{x_0}+(a\ mod\ b)*{y_0} = \gcd(b,a\ mod\ b)
b∗x0+(a mod b)∗y0=gcd(b,a mod b) 对
(
a
m
o
d
b
)
(a\ mod\ b)
(a mod b) 展开有：
a
m
o
d
b
=
a
−
b
∗
[
a
b
]
a\ mod\ b = a-b*[\frac{a}{b}]
a mod b=a−b∗[ba] 代入有：
b
∗
x
0
+
(
a
−
b
∗
[
a
b
]
)
∗
y
0
=
gcd
(
b
,
a
m
o
d
b
)
b*x_0+(a-b*[\frac{a}{b}])*y_0 = \gcd(b,a\ mod\ b)
b∗x0+(a−b∗[ba])∗y0=gcd(b,a mod b) 分理出 x，y：
a
∗
y
0
+
b
∗
(
x
0
−
[
a
b
]
∗
y
0
)
=
gcd
(
b
,
a
m
o
d
b
)
=
gcd
(
a
,
b
)
a*y_0 + b*(x_0-[\frac{a}{b}]*y_0)= \gcd(b,a\ mod\ b) = \gcd(a,b)
a∗y0+b∗(x0−[ba]∗y0)=gcd(b,a mod b)=gcd(a,b) 令，
x
′
=
y
0
,
y
′
=
x
0
−
[
a
b
]
∗
y
0
x'= y_0,y' = x_0-[\frac{a}{b}]*y_0
x′=y0,y′=x0−[ba]∗y0, 代入上式：
a
∗
x
′
+
b
∗
y
′
=
gcd
(
a
,
b
)
a*x'+b*y' = \gcd (a,b)
a∗x′+b∗y′=gcd(a,b) 通过以上方式，可以运用数学归纳法，得证扩展欧几里得。
代码实现
在欧几里得的基础上，传入 x，y，运用：
x
′
=
y
,
y
′
=
x
−
[
a
b
]
∗
y
x'= y,y' = x-[\frac{a}{b}]*y
x′=y,y′=x−[ba]∗y 即可递推得的到系数 x，y。
代码
int extend_gcd(int a, int b, int& x, int& y)// 函数返回 a，最大公约数
{if (!b) {
x = 1, y = 0;
return a;
}
int d = gcd(b, a % b, x, y);
int t = x;// 临时记录 x
// 利用：x'= y,y' = x-[a/b]*y
x = y;
y = t - y * (a / b);
return d;
}
线性同余方程
定义
对于整数 a，b，m，满足：
a
∗
x
≡
b
(
m
o
d
m
)
a*x \equiv b\qquad (mod\ m)
a∗x≡b(mod m) 求整数 x（有解或无解）。由于未知数最高次为 1，因此又被称为一次同余方程。
求解
由定义式易知：
a
∗
x
−
b
a*x-b
a∗x−b 是 m 的倍数，不妨设商为
−
y
-y
−y 对定义式去模运算：
a
∗
x
+
m
∗
y
=
b
a*x+m*y = b
a∗x+m∗y=b 则原方程的解等价于求满足上式的 x 的值。
方程有解等价于：
b
∣
g
c
d
(
a
,
m
)
b\mid gcd(a,m)
b∣gcd(a,m)
因此可以借助扩展欧几里得进行求解
代码
int solve(int a, int m, int& x, int& y)
{if (!m) {
x = 1, y = 0;
return a;
}
int d = solve(m, a % m, x, y);
int t = x;
y = x;
x = t - (a / m) * y;
return d;
}
bool check(int m,int d)
{return m % d == 0;}
void answer(int a,int m)
{
int x, y;
int d = solve(a, m, x, y);
int answer;
if (check(m, d))
answer = (x % m + m) % m;
else
puts("impossible");
}
线性同余方程组
定义
对于 n 对模数与被模数
a
i
,
m
i
a_i,m_i
ai,mi, 有：
x
≡
a
1
(
m
o
d
m
1
)
x \equiv a_1\qquad (mod\ m_1)
x≡a1(mod m1)
x
≡
a
2
(
m
o
d
m
2
)
x \equiv a_2\qquad (mod\ m_2)
x≡a2(mod m2)
.
.
.
...
...
x
≡
a
n
(
m
o
d
m
n
)
x \equiv a_n\qquad (mod\ m_n)
x≡an(mod mn)
求解
中国剩余定理 设
m
,
M
i
m,M_i
m,Mi 为
m
=
∏
i
=
1
n
m
i
m = \prod_{i=1}^{n}{m_{i}}
m=i=1∏nmi
M
i
=
m
m
i
M_i = \frac{m}{m_i}
Mi=mim 若
m
i
m_i
mi 之间两两互质，设
t
i
t_i
ti 为：（
M
i
−
1
M_i^{-1}
Mi−1）
M
i
∗
t
i
≡
1
(
m
o
d
m
i
)
M_i*t_i \equiv 1\qquad(mod\ m_i)
Mi∗ti≡1(mod mi) 解
x
x
x 为：
x
=
∑
i
=
1
n
a
i
⋅
M
i
⋅
t
i
x = \sum_{i\; =\; 1}^{n}{a_{i}\cdot M_{i}\cdot t_{i}}
x=i=1∑nai⋅Mi⋅ti
证明——（来自 李煜东 《算法竞赛进阶指南》）
m 不满足互余下的通解
取出前两个式子：
x
≡
a
1
(
m
o
d
m
1
)
x \equiv a_1\qquad (mod\ m_1)
x≡a1(mod m1)
x
≡
a
2
(
m
o
d
m
2
)
x \equiv a_2\qquad (mod\ m_2)
x≡a2(mod m2) 去模处理：
x
=
k
1
∗
a
1
+
m
1
x = k_1*a_1 + m_1
x=k1∗a1+m1
x
=
k
2
∗
a
2
+
m
2
x = k_2*a_2 + m_2
x=k2∗a2+m2 联立并化简：
k
1
∗
a
1
−
k
2
∗
a
2
=
m
2
−
m
1
k_1*a_1-k_2*a_2 = m_2-m_1
k1∗a1−k2∗a2=m2−m1 根据扩展欧几里得, 求解
k
1
,
k
2
k_1,k_2
k1,k2 不定方程
x
=
k
1
∗
a
1
+
m
1
x = k_1*a_1 + m_1
x=k1∗a1+m1 的解为：
x
=
(
k
1
+
k
a
1
g
c
d
(
a
1
,
a
2
)
)
∗
a
1
+
m
1
x = (k_1+k\frac{a_1}{gcd(a_1,a_2)})*a_1+m_1
x=(k1+kgcd(a1,a2)a1)∗a1+m1 化简：
x
=
a
1
∗
k
1
+
m
1
+
k
∗
l
c
m
(
a
1
,
a
2
)
x = a_1*k_1+m_1+k*lcm(a_1,a_2)
x=a1∗k1+m1+k∗lcm(a1,a2) 令
m
=
a
1
∗
k
1
+
m
1
,
a
=
l
c
m
(
a
1
,
a
2
)
m = a_1*k_1+m_1,a = lcm(a_1,a_2)
m=a1∗k1+m1,a=lcm(a1,a2)
x
=
k
∗
a
+
m
x =k*a+ m
x=k∗a+m 因此方程组中所有式子两两合并，n-1 次后最终可以化为一个形如
x
=
k
∗
a
′
+
m
′
x =k*a'+m'
x=k∗a′+m′ 的等式。 最终求解：
x
m
o
d
a
′
≡
m
′
x\ mod\ a'\equiv m'
x mod a′≡m′ 中 x 的解，等价于：
m
m
o
d
a
m\ mod \ a
m mod a的最小正整数。
代码
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y)
{
if (!b) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, x, y);
LL t = x;
x = y;
y = t - (a / b) * y;
return d;
}
LL mod(LL a, LL b)
{
return ((a % b) + b) % b;
}
int main()
{
int n;
scanf("%d", &n);
LL a, m;
bool flag = true;
scanf("%lld%lld", &a, &m);//先读入第一个式子
n--;
//读入剩余的并合并
while (n--) {
LL a0, m0;
scanf("%lld%lld", &a0, &m0);
LL k1, k2;
LL d = exgcd(a, -a0, k1, k2);
if ((m0 - m) % d) {//如果同余方程无解
flag = false;
break;
}
k1 = mod(k1 * (m0 - m) / d, abs(a0 / d));//防止溢出
m = a * k1 + m;//合并后的m = a*k1+m
a = abs(a / d * a0);//合并后的a = lcm(a,a0）
}
if (flag)
printf("%lld", mod(m, a));
else
puts("-1");
return 0;
}