来源

中国剩余定理，英文为 Chinese Remainder Theorem\text{Chinese Remainder Theorem}，简称 CRT\text{CRT}。最早见于《孙子算经》中：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”故又称孙子定理。

算法简介

适用条件

中国剩余定理可求解如下的一元线性同余方程组，其中 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n 两两互质。

$$ (S):\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 两两互质，则对任意的整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，方程组 (S)(S) 有解。可以通过如下方式构造得到：

  1. 设 M=∏i=1nmiM=\prod\limits_{i=1}^n m_i，Mi=MmiM_i=\frac{M}{m_i}。
  2. 设整数 tit_i 为模 mim_i 意义下 MiM_i 的逆元，即 Miti≡1( mod mi)M_it_i\equiv1\quad(\bmod m_i)。
  3. 方程组 (S)(S) 的通解为 x=kM+∑i=1naitiMi,k∈Zx=kM+\sum\limits_{i=1}^n a_it_iM_i,k\in Z；在模 MM 的意义下，方程组只有一个解 x=(∑i=1naitiMi) mod Mx=\left(\sum\limits_{i=1}^n a_it_iM_i\right)\bmod M。

略证

从假设可知，对任何 $i\in\{1,2,\cdots,n\}$，由于 $\forall j\in\{1,2,\cdots,n\},j\ne i$，有 gcd⁡(mi,mj)=1\gcd(m_i,m_j)=1，所以 gcd⁡(mi,Mi)=1\gcd(m_i,M_i)=1。根据裴蜀定理，存在整数 tit_i，使得 Miti≡1( mod mi)M_it_i\equiv1\quad(\bmod m_i)。
由于 Miti≡1( mod mi)M_it_i\equiv1(\bmod m_i)，故 aitiMi≡ai⋅1≡ai( mod mi)a_it_iM_i\equiv a_i\cdot1\equiv a_i(\bmod m_i)；又 ∀i∈{1,2,⋯ ,n}\forall i\in\{1,2,\cdots,n\}，且 i≠ji\ne j，ajtjMj≡0( mod mi)a_jt_jM_j\equiv0(\bmod m_i)。所以 ∑i=1naitiMi≡\sum\limits_{i=1}^n a_it_iM_i\equivaitiMi+∑j=1i−1ajtjMj+∑j=i+1najtjMja_it_iM_i+\sum\limits_{j=1}^{i-1}a_jt_jM_j+\sum\limits_{j=i+1}^n a_jt_jM_j≡\equivai+∑j=1i−10a_i+\sum\limits_{j=1}^{i-1}0∑j=i+1n0≡ai( mod mi)\sum\limits_{j=i+1}^n 0\equiv a_i\quad(\bmod m_i)。
以上已经证明：x=∑i=1naitiMix=\sum\limits_{i=1}^n a_it_iM_i 是方程组的一个解。 假设方程组存在两个解 x1,x2x_1,x_2，那么 ∀i∈\forall i\in$\{1,2,\cdots,n\}$，有 x1−x2≡0( mod mi)x_1-x_2\equiv0\quad(\bmod m_i)；又 m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n 两两互质，说明 M∣(x1−x2)M\mid(x_1-x_2)；所以方程组 (S)(S) 的两个解必然相差 MM 的整数倍。由于存在一个特解 x=x=∑i=1naitiMi\sum\limits_{i=1}^n a_it_iM_i，所以方程组 (S)(S) 的通解为 x=kM+∑i=1naitiMi,k∈Zx=kM+\sum\limits_{i=1}^n a_it_iM_i,k\in Z。
证毕。
（定理描述和证明部分引用维基百科词条：中国剩余定理）

洛谷P1495 【模板】中国剩余定理(CRT)/曹冲养猪 ↬\looparrowright

题目描述

自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 1616 头母猪，如果建了 33 个猪圈，剩下 11 头猪就没有地方安家了。如果建造了 55 个猪圈，但是仍然有 11 头猪没有地方去，然后如果建造了 77 个猪圈，还有 22 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 nn——建立猪圈的次数，接下来 nn 行，每行两个整数 aia_i，bib_i， 表示建立了 aia_i 个猪圈，有 bib_i 头猪没有去处。你可以假定 aia_i，aja_j 互质。

输出格式

输出包含一个正整数，即为曹冲至少养母猪的数目。

输入输出样例

输入 #1

3
3 1
5 1
7 2

输出 #1

16

说明/提示

1≤n≤101 \leq n\le10，1≤bi≤ai≤1000001 \leq b_i\le a_i\le100000，1≤∏i=1nai≤10181 \leq \prod\limits_{i=1}^n a_i \leq 10^{18}。

分析

由题意得一元线性同余方程组 $\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.$，题干中已经说明 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 两两互质，因此可用中国剩余定理求解这个方程组。
设 M=∑i=1naiM=\sum\limits_{i=1}^n a_i，Mi=MaiM_i=\frac{M}{a_i}；那么一定存在正整数 tit_i 使得 Miti≡1( mod ai)M_it_i\equiv1\quad(\bmod a_i)。
方程组的最小正整数解为 x=(∑i=1nbitiMi) mod Mx=\left(\sum\limits_{i=1}^n b_it_iM_i\right)\bmod M。

代码

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
#include<iostream>
#include<cstdio>
#define ll long long
#define N 12
using namespace std;
int n;
ll a[N],b[N];
inline void ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return;
	}
	ex_gcd(b,a%b,x,y);
	ll temp=x;
	x=y;
	y=temp-a/b*y;
}
void CRT()
{
	int i;
	ll mul=1;
	ll ans=0;
	for(i=1;i<=n;i++) mul=mul*a[i];
	for(i=1;i<=n;i++)
	{
		ll Mi=mul/a[i];
		ll x,y;
		//----------------------
		//扩展欧几里得算法
		//求Mi模a[i]意义下的逆元
		ex_gcd(Mi,a[i],x,y);
		x=(x+a[i])%a[i];
		//----------------------
		ans=ans+b[i]*Mi*x;
	}
	cout<<ans%mul<<endl;
}
int main()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) scanf("%lld%lld",a+i,b+i);
	CRT();
	return 0;
}