Tip：建议读者不要太着急后翻，按照顺序阅读有助于理解
中国剩余定理(CRT)
问题引出
“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。——百度百科
前置知识
数学基础
依题意可得：
{
x
≡
2
(
m
o
d
?
3
)
x
≡
3
(
m
o
d
?
5
)
x
≡
2
(
m
o
d
?
7
)
\left\{\begin{matrix}x\equiv 2(mod\ 3)\\x\equiv 3(mod\ 5)\\x\equiv 2(mod\ 7)\end{matrix}\right.
????x≡2(mod?3)x≡3(mod?5)x≡2(mod?7)?
要求求出
x
x
x 。三个方程式放在一起不好想，先拆开，变成三条方程：
x
1
≡
2
(
m
o
d
?
3
)
x
2
≡
3
(
m
o
d
?
5
)
x
3
≡
2
(
m
o
d
?
7
)
x_1\equiv 2(mod\ 3)\\x_2\equiv 3(mod\ 5)\\x_3\equiv 2(mod\ 7)
x1?≡2(mod?3)x2?≡3(mod?5)x3?≡2(mod?7)
现在，假设：
x
1
+
x
2
≡
2
(
m
o
d
?
3
)
,
x
1
+
x
3
≡
2
(
m
o
d
?
3
)
x_1+x_2\equiv 2(mod\ 3),x_1+x_3\equiv 2(mod\ 3)
x1?+x2?≡2(mod?3),x1?+x3?≡2(mod?3)
x
2
+
x
1
≡
3
(
m
o
d
?
5
)
,
x
2
+
x
3
≡
3
(
m
o
d
?
5
)
x_2+x_1\equiv 3(mod\ 5),x_2+x_3\equiv 3(mod\ 5)
x2?+x1?≡3(mod?5),x2?+x3?≡3(mod?5)
x
3
+
x
1
≡
2
(
m
o
d
?
7
)
,
x
3
+
x
2
≡
2
(
m
o
d
?
7
)
x_3+x_1\equiv 2(mod\ 7),x_3+x_2\equiv 2(mod\ 7)
x3?+x1?≡2(mod?7),x3?+x2?≡2(mod?7)
那么：
∵
x
1
≡
x
1
+
0
≡
x
1
+
x
2
≡
x
1
+
x
3
≡
2
(
m
o
d
?
3
)
\because x_1\equiv x_1+0\equiv x_1+x_2\equiv x_1+x_3\equiv2(mod\ 3)
∵x1?≡x1?+0≡x1?+x2?≡x1?+x3?≡2(mod?3)
∴
x
2
≡
x
3
≡
0
(
m
o
d
?
3
)
\therefore x_2\equiv x_3\equiv 0(mod\ 3)
∴x2?≡x3?≡0(mod?3)
∴
3
∣
x
2
,
3
∣
x
3
\therefore 3|x_2,3|x_3
∴3∣x2?,3∣x3?
∵
x
2
≡
x
2
+
0
≡
x
2
+
x
1
≡
x
2
+
x
3
≡
3
(
m
o
d
?
5
)
\because x_2\equiv x_2+0\equiv x_2+x_1\equiv x_2+x_3\equiv3(mod\ 5)
∵x2?≡x2?+0≡x2?+x1?≡x2?+x3?≡3(mod?5)
∴
x
1
≡
x
3
≡
0
(
m
o
d
?
5
)
\therefore x_1\equiv x_3\equiv 0(mod\ 5)
∴x1?≡x3?≡0(mod?5)
∴
5
∣
x
1
,
5
∣
x
3
\therefore 5|x_1,5|x_3
∴5∣x1?,5∣x3?
∵
x
3
≡
x
3
+
0
≡
x
3
+
x
1
≡
x
3
+
x
2
≡
2
(
m
o
d
?
7
)
\because x_3\equiv x_3+0\equiv x_3+x_1\equiv x_3+x_2\equiv2(mod\ 7)
∵x3?≡x3?+0≡x3?+x1?≡x3?+x2?≡2(mod?7)
∴
x
1
≡
x
2
≡
0
(
m
o
d
?
7
)
\therefore x_1\equiv x_2\equiv 0(mod\ 7)
∴x1?≡x2?≡0(mod?7)
∴
7
∣
x
1
,
7
∣
x
2
\therefore 7|x_1,7|x_2
∴7∣x1?,7∣x2?
我们发现，如果这样假设，那么
x
1
+
x
2
+
x
3
x_1+x_2+x_3
x1?+x2?+x3? 就会是方程的一个解：
∵
x
2
≡
x
3
≡
0
(
m
o
d
?
3
)
\because x_2\equiv x_3\equiv 0(mod\ 3)
∵x2?≡x3?≡0(mod?3)
∴
x
1
+
x
2
+
x
3
≡
x
1
≡
2
(
m
o
d
?
3
)
\therefore x_1+x_2+x_3\equiv x_1\equiv2(mod\ 3)
∴x1?+x2?+x3?≡x1?≡2(mod?3)
∵
x
1
≡
x
3
≡
0
(
m
o
d
?
5
)
\because x_1\equiv x_3\equiv 0(mod\ 5)
∵x1?≡x3?≡0(mod?5)
∴
x
1
+
x
2
+
x
3
≡
x
2
≡
3
(
m
o
d
?
5
)
\therefore x_1+x_2+x_3\equiv x_2\equiv3(mod\ 5)
∴x1?+x2?+x3?≡x2?≡3(mod?5)
∵
x
1
≡
x
2
≡
0
(
m
o
d
?
7
)
\because x_1\equiv x_2\equiv 0(mod\ 7)
∵x1?≡x2?≡0(mod?7)
∴
x
1
+
x
2
+
x
3
≡
x
3
≡
2
(
m
o
d
?
7
)
\therefore x_1+x_2+x_3\equiv x_3\equiv2(mod\ 7)
∴x1?+x2?+x3?≡x3?≡2(mod?7)
满足题意，那么现在就只需要找出求解
x
1
,
x
2
,
x
3
x_1,x_2,x_3
x1?,x2?,x3? 的方法。设
x
1
=
5
×
7
×
k
1
=
35
k
1
,
x
2
=
3
×
7
×
k
2
=
21
k
2
,
x
3
=
3
×
5
×
k
3
=
15
k
3
x_1=5\times 7\times k_1=35k_1,x_2=3\times 7\times k_2=21k_2,x_3=3\times 5\times k_3=15k_3
x1?=5×7×k1?=35k1?,x2?=3×7×k2?=21k2?,x3?=3×5×k3?=15k3?。将它们分别代入三个式子中：
35
k
1
≡
2
(
m
o
d
?
3
)
35k_1\equiv 2(mod\ 3)
35k1?≡2(mod?3)
21
k
2
≡
3
(
m
o
d
?
5
)
21k_2\equiv 3(mod\ 5)
21k2?≡3(mod?5)
15
k
3
≡
2
(
m
o
d
?
7
)
15k_3\equiv 2(mod\ 7)
15k3?≡2(mod?7)
右边统一化一：
35
k
1
×
1
2
≡
1
(
m
o
d
?
3
)
35k_1\times\frac{1}{2}\equiv 1(mod\ 3)
35k1?×21?≡1(mod?3)
21
k
2
×
1
3
≡
1
(
m
o
d
?
5
)
21k_2\times\frac{1}{3}\equiv 1(mod\ 5)
21k2?×31?≡1(mod?5)
15
k
3
×
1
2
≡
1
(
m
o
d
?
7
)
15k_3\times\frac{1}{2}\equiv 1(mod\ 7)
15k3?×21?≡1(mod?7)
k
1
×
35
2
≡
1
(
m
o
d
?
3
)
k_1\times \frac{35}{2}\equiv 1(mod\ 3)
k1?×235?≡1(mod?3)
k
2
×
21
3
≡
1
(
m
o
d
?
5
)
k_2\times \frac{21}{3}\equiv 1(mod\ 5)
k2?×321?≡1(mod?5)
k
3
×
15
2
≡
1
(
m
o
d
?
7
)
k_3\times \frac{15}{2}\equiv 1(mod\ 7)
k3?×215?≡1(mod?7)
分别求出
k
1
,
k
2
,
k
3
k_1,k_2,k_3
k1?,k2?,k3? 在对应模数意义下的值，再通过它们的值，求出
x
1
,
x
2
,
x
3
x_1,x_2,x_3
x1?,x2?,x3? ，相加，并且
m
o
d
?
3
×
5
×
7
mod\ 3\times5\times7
mod?3×5×7得到它的解在
m
o
d
?
105
mod\ 105
mod?105 意义下，是
23
23
23。
尝试将特殊情况一般化：
假
设
m
中
的
数
两
两
互
质
假设m中的数两两互质
假设m中的数两两互质
{
x
≡
a
1
(
m
o
d
?
m
1
)
x
≡
a
2
(
m
o
d
?
m
2
)
.
.
.
.
.
.
x
≡
a
n
(
m
o
d
?
m
n
)
\left\{\begin{matrix}x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\\......\\x\equiv a_n(mod\ m_n)\end{matrix}\right.
????????x≡a1?(mod?m1?)x≡a2?(mod?m2?)......x≡an?(mod?mn?)?
假
设
对
于
任
意
的
?
i
?
(
1
≤
i
≤
n
)
?
都
有
∏
j
=
1
n
m
j
m
i
∣
x
i
,
则
对
于
任
意
的
?
i
?
(
1
≤
i
≤
n
)
?
都
有
x
i
=
k
i
×
∏
j
=
1
n
m
j
m
i
假设对于任意的\ i\ (1\le i\le n)\ 都有\frac{\prod\limits_{j=1}^nm_j}{m_i}|x_i,则对于任意的\ i\ (1\le i\le n)\ 都有x_i=k_i\times\frac{\prod\limits_{j=1}^nm_j}{m_i}
假设对于任意的?i?(1≤i≤n)?都有mi?j=1∏n?mj??∣xi?,则对于任意的?i?(1≤i≤n)?都有xi?=ki?×mi?j=1∏n?mj??
再
令
M
i
=
∏
j
=
1
n
m
j
m
i
,
带
入
原
式
得
：
再令M_i=\frac{\prod\limits_{j=1}^nm_j}{m_i},带入原式得：
再令Mi?=mi?j=1∏n?mj??,带入原式得：
{
k
1
×
M
1
≡
a
1
(
m
o
d
?
m
1
)
k
2
×
M
2
≡
a
2
(
m
o
d
?
m
2
)
.
.
.
.
.
.
k
n
×
M
3
≡
a
n
(
m
o
d
?
m
n
)
\left\{\begin{matrix}k_1\times M_1\equiv a_1(mod\ m_1)\\k_2\times M_2\equiv a_2(mod\ m_2)\\......\\k_n\times M_3\equiv a_n(mod\ m_n)\end{matrix}\right.
????????k1?×M1?≡a1?(mod?m1?)k2?×M2?≡a2?(mod?m2?)......kn?×M3?≡an?(mod?mn?)?
将
右
边
化
一
：
将右边化一：
将右边化一：
{
k
1
×
M
1
×
1
a
1
≡
1
(
m
o
d
?
m
1
)
k
2
×
M
2
×
1
a
2
≡
1
(
m
o
d
?
m
2
)
.
.
.
.
.
.
k
n
×
M
n
×
1
a
n
≡
1
(
m
o
d
?
m
n
)
\left\{\begin{matrix}k_1\times M_1\times\frac{1}{a_1}\equiv 1(mod\ m_1)\\k_2\times M_2\times\frac{1}{a_2}\equiv 1(mod\ m_2)\\......\\k_n\times M_n\times\frac{1}{a_n}\equiv 1(mod\ m_n)\end{matrix}\right.
????????k1?×M1?×a1?1?≡1(mod?m1?)k2?×M2?×a2?1?≡1(mod?m2?)......kn?×Mn?×an?1?≡1(mod?mn?)?
表
示
出
k
：
表示出k：
表示出k：
{
k
1
≡
1
M
1
×
1
a
1
(
m
o
d
?
m
1
)
k
2
≡
1
M
2
×
1
a
2
(
m
o
d
?
m
2
)
.
.
.
.
.
.
k
n
≡
1
M
n
×
1
a
n
(
m
o
d
?
m
n
)
\left\{\begin{matrix}k_1\equiv \frac{1}{M_1\times\frac{1}{a_1}}(mod\ m_1)\\k_2\equiv \frac{1}{M_2\times\frac{1}{a_2}}(mod\ m_2)\\......\\k_n\equiv \frac{1}{M_n\times\frac{1}{a_n}}(mod\ m_n)\end{matrix}\right.
????????????k1?≡M1?×a1?1?1?(mod?m1?)k2?≡M2?×a2?1?1?(mod?m2?)......kn?≡Mn?×an?1?1?(mod?mn?)?
化
简
：
化简：
化简：
{
k
1
≡
1
M
1
×
1
1
a
1
≡
1
M
1
×
a
1
(
m
o
d
?
m
1
)
k
2
≡
1
M
2
×
1
1
a
2
≡
1
M
2
×
a
2
(
m
o
d
?
m
2
)
.
.
.
.
.
.
k
n
≡
1
M
n
×
1
1
a
n
≡
1
M
n
×
a
n
(
m
o
d
?
m
n
)
\\\left\{\begin{matrix}k_1\equiv \frac{1}{M_1}\times\frac{1}{\frac{1}{a_1}}\equiv\frac{1}{M_1}\times a_1(mod\ m_1)\\k_2\equiv \frac{1}{M_2}\times\frac{1}{\frac{1}{a_2}}\equiv\frac{1}{M_2}\times a_2(mod\ m_2)\\......\\k_n\equiv \frac{1}{M_n}\times\frac{1}{\frac{1}{a_n}}\equiv\frac{1}{M_n}\times a_n(mod\ m_n)\end{matrix}\right.
????????????k1?≡M1?1?×a1?1?1?≡M1?1?×a1?(mod?m1?)k2?≡M2?1?×a2?1?1?≡M2?1?×a2?(mod?m2?)......kn?≡Mn?1?×an?1?1?≡Mn?1?×an?(mod?mn?)?
最 终 答 案 ： x ≡ ∑ i = 1 n k i × M i ( m o d ? ∏ i = 1 n m i ) \boxed{最终答案：x\equiv\sum\limits_{i=1}^nk_i\times M_i(mod\ \prod\limits_{i=1}^nm_i)} 最终答案：x≡i=1∑n?ki?×Mi?(mod?i=1∏n?mi?)?
代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],b[100010],n,Mod=1,ans_i,x,y,gcdab;
void ext_gcd(int a,int b,int &d,int &x,int &y){//exgcd模板
if (b==0){
d=a;x=1;y=0;
return;
}
ext_gcd(b,a%b,d,y,x);
y-=a/b*x;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];//a_i表示除数，b_i表示余数
Mod*=a[i];
}
for(int i=1;i<=n;i++){//结论
int Mod_i=Mod/a[i];
ext_gcd(Mod_i,a[i],gcdab,x,y);//求M_i在mod m_i意义下的逆元
int ny_M_i=(x+a[i])%a[i];
int k=ny_M_i*b[i]%a[i];
ans_i=(ans_i+k*Mod_i)%Mod;
}
cout<<ans_i%Mod;
return 0;
}
扩展中国剩余定理(EXCRT)
问题引出
上述的方法只能解决所有模数互质的情况，否则就无法求出 1 M n ( m o d ? ∏ i = 1 n m i ) \frac{1}{M_n}(mod\ \prod\limits_{i=1}^nm_i) Mn?1?(mod?i=1∏n?mi?) 了，为了处理不保证所有模数互质的情况，便有了“扩展中国剩余定理”。
前置知识
数学基础
扩展中国剩余定理的核心思想，就是不断合并方程（一次合并两个），当所有的方程都被合并成为一个时，这个方程就是所有方程的解集。
那么如和将两个方程合并？举个例子：
{
x
≡
a
1
(
m
o
d
?
m
1
)
x
≡
a
2
(
m
o
d
?
m
2
)
\left\{\begin{matrix}x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\end{matrix}\right.
{x≡a1?(mod?m1?)x≡a2?(mod?m2?)?
如果设
k
1
∈
N
,
k
2
∈
N
,
x
=
k
1
m
1
+
a
1
,
x
=
k
2
m
2
+
a
2
k_1\in\mathbb{N},k_2\in\mathbb{N},x=k_1m_1+a_1,x=k_2m_2+a_2
k1?∈N,k2?∈N,x=k1?m1?+a1?,x=k2?m2?+a2?
那么
k
1
m
1
+
a
1
=
k
2
m
2
+
a
2
k_1m_1+a_1=k_2m_2+a_2
k1?m1?+a1?=k2?m2?+a2?
∴
k
1
m
1
?
k
2
m
2
=
a
2
?
a
1
\therefore k_1m_1-k_2m_2=a_2-a_1
∴k1?m1??k2?m2?=a2??a1?
∴
k
1
m
1
g
c
d
(
m
1
,
m
2
)
+
(
?
k
2
m
2
g
c
d
(
m
1
,
m
2
)
)
=
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
\therefore k_1\frac{m_1}{gcd(m_1,m_2)}+(-k_2\frac{m_2}{gcd(m_1,m_2)})=\frac{a_2-a_1}{gcd(m_1,m_2)}
∴k1?gcd(m1?,m2?)m1??+(?k2?gcd(m1?,m2?)m2??)=gcd(m1?,m2?)a2??a1??
∴
k
1
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
×
m
1
g
c
d
(
m
1
,
m
2
)
+
(
k
2
?
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
×
m
2
g
c
d
(
m
1
,
m
2
)
)
=
1
\therefore \frac{k_1}{\frac{a_2-a_1}{gcd(m_1,m_2)}}\times\frac{m_1}{gcd(m_1,m_2)}+\left(\frac{k_2}{-\frac{a_2-a_1}{gcd(m_1,m_2)}}\times\frac{m_2}{gcd(m_1,m_2)}\right)=1
∴gcd(m1?,m2?)a2??a1??k1??×gcd(m1?,m2?)m1??+(?gcd(m1?,m2?)a2??a1??k2??×gcd(m1?,m2?)m2??)=1
方程中，
m
1
,
m
2
,
g
c
d
(
m
1
,
m
2
)
m_1,m_2,gcd(m_1,m_2)
m1?,m2?,gcd(m1?,m2?) 都是我们已知的量。这便是一个非常典型的
e
x
g
c
d
exgcd
exgcd。不明显？那我们令
a
=
m
1
g
c
d
(
m
1
,
m
2
)
,
b
=
m
2
g
c
d
(
m
1
,
m
2
)
,
x
′
=
k
1
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
,
y
′
=
k
2
?
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
a=\frac{m_1}{gcd(m_1,m_2)},b=\frac{m_2}{gcd(m_1,m_2)},x'=\frac{k_1}{\frac{a_2-a_1}{gcd(m_1,m_2)}},y'=\frac{k_2}{-\frac{a_2-a_1}{gcd(m_1,m_2)}}
a=gcd(m1?,m2?)m1??,b=gcd(m1?,m2?)m2??,x′=gcd(m1?,m2?)a2??a1??k1??,y′=?gcd(m1?,m2?)a2??a1??k2?? 原方程变为：
a
x
′
+
b
y
′
=
1
ax'+by'=1
ax′+by′=1
之后再通过
e
x
g
c
d
exgcd
exgcd 求出方程的解，则
{
k
1
=
x
′
×
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
k
2
=
y
′
×
(
?
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
)
\left\{\begin{matrix}k_1=x'\times\frac{a_2-a_1}{gcd(m_1,m_2)}\\k_2=y'\times\left(-\frac{a_2-a_1}{gcd(m_1,m_2)}\right)\end{matrix}\right.
{k1?=x′×gcd(m1?,m2?)a2??a1??k2?=y′×(?gcd(m1?,m2?)a2??a1??)?
∴
x
=
x
′
×
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
×
m
1
+
a
1
=
y
′
×
(
?
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
)
×
m
2
+
a
2
\therefore x=x'\times\frac{a_2-a_1}{gcd(m_1,m_2)}\times m_1+a_1=y'\times\left(-\frac{a_2-a_1}{gcd(m_1,m_2)}\right)\times m_2+a_2
∴x=x′×gcd(m1?,m2?)a2??a1??×m1?+a1?=y′×(?gcd(m1?,m2?)a2??a1??)×m2?+a2?
在有了一个特解
x
?
x^*
x? 则其通解（在
m
o
d
?
l
c
m
(
m
1
,
m
2
)
mod\ lcm(m_1,m_2)
mod?lcm(m1?,m2?) 意义下）为
x
+
k
×
l
c
m
(
m
1
,
m
2
)
(
k
∈
N
)
x+k\times lcm(m1,m2)(k\in\mathbb{N})
x+k×lcm(m1,m2)(k∈N)
再将合并两个方程的方法便是：
在
?
{
x
≡
a
1
(
m
o
d
?
m
1
)
x
≡
a
2
(
m
o
d
?
m
2
)
?
中
?
x
≡
x
′
×
a
2
?
a
1
g
c
d
(
m
1
,
m
2
)
×
m
1
+
a
1
?
(
?
x
′
为
方
程
m
1
g
c
d
(
m
1
,
m
2
)
x
′
+
m
2
g
c
d
(
m
1
,
m
2
)
y
′
=
1
?
中
的
x
′
)
在\ \left\{\begin{matrix}x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\end{matrix}\right.\ 中\ x\equiv x'\times\frac{a_2-a_1}{gcd(m_1,m_2)}\times m_1+a_1\ (\ x'为方程\frac{m_1}{gcd(m_1,m_2)}x'+\frac{m_2}{gcd(m_1,m_2)}y'=1\ 中的x')
在?{x≡a1?(mod?m1?)x≡a2?(mod?m2?)??中?x≡x′×gcd(m1?,m2?)a2??a1??×m1?+a1??(?x′为方程gcd(m1?,m2?)m1??x′+gcd(m1?,m2?)m2??y′=1?中的x′)
若有
n
n
n 个这样的方程：
∴
若
将
{
x
≡
a
1
(
m
o
d
?
m
1
)
x
≡
a
2
(
m
o
d
?
m
2
)
.
.
.
.
.
.
x
≡
a
n
(
m
o
d
?
m
n
)
中
的
x
分
别
设
为
X
1
,
X
2
,
.
.
.
,
X
n
,
设
M
i
=
l
c
m
(
M
i
?
1
,
m
i
)
(
2
≤
i
≤
n
)
,
M
1
=
m
1
,
A
i
=
x
′
×
a
i
?
A
i
?
1
g
c
d
(
M
i
?
1
,
m
i
)
×
M
i
?
1
+
A
i
?
1
(
2
≤
i
≤
n
)
,
A
1
=
a
1
\therefore 若将\left\{\begin{matrix}x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\\......\\x\equiv a_n(mod\ m_n)\end{matrix}\right.中的x分别设为X_1,X_2,...,X_n,设M_i=lcm(M_{i-1},m_i)(2\le i\le n),M_1=m_1,A_i=x'\times\frac{a_i-A_{i-1}}{gcd(M_{i-1},m_i)}\times M_{i-1}+A_{i-1}(2\le i\le n),A_1=a_1
∴若将????????x≡a1?(mod?m1?)x≡a2?(mod?m2?)......x≡an?(mod?mn?)?中的x分别设为X1?,X2?,...,Xn?,设Mi?=lcm(Mi?1?,mi?)(2≤i≤n),M1?=m1?,Ai?=x′×gcd(Mi?1?,mi?)ai??Ai?1??×Mi?1?+Ai?1?(2≤i≤n),A1?=a1?
答
案
便
是
x
≡
X
n
(
m
o
d
?
M
n
)
答案便是x\equiv X_n(mod\ M_n)
答案便是x≡Xn?(mod?Mn?)
代码实现
#include<bits/stdc++.h>
#define int __int128_t
using namespace std;
int n,a[100010][2],sum=1,ans,xx,yy,q,h,ys1,ys2;
bool f;
int read()//快读
{
int X=0;
bool flag=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
flag=0;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
X=(int)(X<<1)+(X<<3)+ch-'0';
ch=getchar();
}
if(flag)
return X;
return (int)~(X-1);
}
void output(int X)//快输
{
if(X<0){
X=~(X-1);
putchar('-');
}
if(X>9)
output(X/10);
putchar(X%10+'0');
}
int exgcd(int a,int b)//exgcd模板
{
if(!b){
xx=1,yy=0;
return a;
}
ans=exgcd(b,a%b);
int last=xx;
xx=yy;
yy=(int)last-(a/b)*yy;
return ans;
}
int excrt()
{
q=a[1][1],ys1=a[1][0];
for(int i=2;i<=n;i++){
h=a[i][1],ys2=a[i][0];
int r=h-q,gcd_ys=exgcd(ys1,ys2);
if(r%gcd_ys!=0)
return -1;
else{
xx=(int)((xx*r/gcd_ys)%(ys2/gcd_ys)+(ys2/gcd_ys))%(ys2/gcd_ys);//得到k
q=(int)xx*ys1+q;//余数合并
ys1=(int)(ys1*ys2)/gcd_ys;//合并除数
}
}
return q;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++){
a[i][0]=read();//a_{i,0}表示除数
a[i][1]=read();//a_{i,1}表示余数
}
output((int)excrt());
return 0;
}
