简介

对于一元线性同余方程组 $\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv a_{n}\left(\bmod m_{n}\right) \end{array}\right.$，中国剩余定理的适用条件是 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n 两两互质。
扩展中国剩余定理适用于 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n 不是两两互质的情况。

求解

考虑前方程组前两个方程，$\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right)\end{array}\right.$，一定存在整数 p,qp,q，使得 x=m1p+a1=m2q+a2x=m_1p+a_1=m_2q+a_2，即 m1p+a1=m2q+a2m_1p+a_1=m_2q+a_2，移项后得到 m1p−m2q=a2−a1m_1p-m_2q=a_2-a_1。结合方程组前二式，得到一个裴蜀等式，由裴蜀定理，当且仅当 gcd⁡(m1,m2)∣(a2−a1)\gcd(m_1,m_2)\mid(a_2-a_1) 时方程有解。
假设得到的裴蜀等式有解，p0p_0 为方程 m1x+m2y=gcd⁡(m1,m2)m_1x+m_2y=\gcd(m_1,m_2) 的特解，那么 pp 的通解为 p=p=a2−a1gcd⁡(m1,m2)p0\frac{a_2-a_1}{\gcd(m_1,m_2)}p_0+km2gcd⁡(m1,m2)(k∈Z)+k\frac{m_2}{\gcd(m_1,m_2)}(k\in Z)。所以 x=m1p+a1=a2−a1gcd⁡(m1,m2)m1p0+a1+k lcm(m1,m2)x=m_1p+a_1=\frac{a_2-a_1}{\gcd(m_1,m_2)}m_1p_0+a_1+k\ \text{lcm}(m_1,m_2)。合并后的通解为 x≡a2−a1gcd⁡(m1,m2)m1p0+a1(modlcm(m1,m2))x\equiv \frac{a_2-a_1}{\gcd(m_1,m_2)}m_1p_0+a_1\pmod{\text{lcm}(m_1,m_2)}。
综上所述，使用 nn 次扩展欧几里得算法，不断合并同余式，最后的余项即为答案。

模板

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#define ll long long
#define N 100003
using namespace std;
int n;
ll a[N],m[N];
//---------------------------------------
//扩展欧几里得算法
//用于将两个线性同余方程合并
inline ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	ll g=ex_gcd(b,a%b,x,y);
	ll temp=x;
	x=y;
	y=temp-a/b*y;
	return g;
}
//---------------------------------------
//---------------------------------------
//扩展中国剩余定理
//不断合并两个线性同余方程
//最后的A即为最小正整数解
void ex_CRT()
{
	ll M=m[1],A=a[1];
	int i;
	for(i=2;i<=n;i++)
	{
		ll p,q;
		ll g=ex_gcd(M,m[i],p,q);
		if((a[i]-A)%g) //无解
		{
			puts("-1");
			return;
		}
		p=(a[i]-A)/g*p;
		//将p取为正解
		p=(p%(m[i]/g)+m[i]/g)%(m[i]/g);
		//合并后，方程未知数x与A模M同余
		A=M*p+A;//m1p+a1
		M=M/g*m[i];//lcm(m1,m2)
		//对A取模
		A=(A%M+M)%M;
	}
	cout<<A<<endl;
}
//----------------------------------------
int main()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) scanf("%lld%lld",m+i,a+i);
	ex_CRT();
	return 0;
}

洛谷P4777 【模板】扩展中国剩余定理（EXCRT）↬\looparrowright

题目描述

给定 nn 组非负整数 ai,bia_i, b_i，求解关于 xx 的方程组的最小非负整数解。

$$ \left\{\begin{array}{c} x \equiv b_{1}\left(\bmod a_{1}\right) \\ x \equiv b_{2}\left(\bmod a_{2}\right) \\ \vdots \\ x \equiv b_{n}\left(\bmod a_{n}\right) \end{array}\right. $$

输入格式

输入第一行包含整数 nn。
接下来 nn 行，每行两个非负整数 ai,bia_i, b_i。

输出格式

输出一行，为满足条件的最小非负整数 xx。

输入输出样例

输入 #1

3
11 6
25 9
33 17

输出 #1

809

说明/提示

对于 $100 \%$ 的数据，1≤n≤1051 \le n \le {10}^5，1≤ai≤10121 \le a_i \le {10}^{12}，0≤bi<ai0 \le b_i < a_i，保证所有 aia_i 的最小公倍数不超过 1018{10}^{18}。
请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。
数据保证有解。

分析

扩展欧几里得算法模板题，乘法运算时有可能爆 long long\text{long long}，需要使用 __int128\text{int128}。__int128\text{int128} 最大可达 2128≈3.4×10392^{128}\approx 3.4\times 10^{39}。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<iostream>
#define ll long long
#define BigInt __int128
#define N 100002
using namespace std;
int n;
ll a[N],b[N];
inline BigInt ex_gcd(BigInt a,BigInt b,BigInt &x,BigInt &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	BigInt g=ex_gcd(b,a%b,x,y);
	BigInt temp=x;
	x=y;
	y=temp-a/b*y;
	return g;
}
void ex_CRT()
{
	BigInt A=a[1],B=b[1];
	int i;
	for(i=2;i<=n;i++)
	{
		BigInt p,q;
		BigInt g=ex_gcd(A,a[i],p,q);
		if((b[i]-B)%g) 
		{
			puts("-1");
			return;
		}
		p=(b[i]-B)/g*p;
		p=(p%(a[i]/g)+a[i]/g)%(a[i]/g);
		B=A*p+B;
		A=A/g*a[i];
		B=(B%A+A)%A;
	}
	cout<<(ll)B<<endl;//转为long long输出
}
int main()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) scanf("%lld%lld",a+i,b+i);
	ex_CRT();
	return 0;
}