这篇文章主要介绍中国剩余定理及其解法以及代码实现

中国剩余定理

引子：曹冲养猪

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

类似此类问题我们可以使用中国剩余定理求解
限制条件模两两互质

推导

推导过程来源于百度百科(主要是太菜了不会推导)

求解模板

以如下问题为例
问：有数模3余2，模5余3，模7余2，问数几何？

  • 衍数：lcm/除数
  • 逆元：为衍数模除数意义下的数论倒数，设衍数为a,除数为b，则逆元为ax ≡ 1(mod b)的最小正整数解
  • 各总：余数 * 衍数 * 逆元
除数 余数 除数最小公倍数(lcm) 衍数 逆元 各总
3 2 105 35 2 140
5 3 105 21 1 63
7 2 105 15 1 30

将"各总"相加得到特解233
最后将233对lcm取模得到最小正整数解23
23即为所求

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
void init(){
	x=0,y=0;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) m[i]=read(),ai[i]=read();
	ll M=1;
	for(int i=1;i<=n;i++) M*=(ll)m[i];//求lcm 
	for(int i=1;i<=n;i++) mi[i]=M/m[i];//求衍数 
	//求逆元
	for(int i=1;i<=n;i++){exgcd(mi[i],m[i],x,y);ti[i]=(x%m[i]+m[i])%m[i];init();}
	ll minx=0;
	for(int i=1;i<=n;i++) minx+=(mi[i]*ai[i]*ti[i])%M;
	printf("%lld",minx%M);
	return 0;
}