题解：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

题目传送门

中国剩余定理（Chinese Remainder Theorem, CRT）是数论中的一个重要定理，用于解决一组同余方程的问题。它在密码学、计算机科学等领域有广泛应用。

定理内容

给定一组两两互质的正整数 $n_1,n_2,\dots ,n_k$，以及任意整数 $a_1,a_2,\dots ,a_k$，存在一个整数 $x$，满足以下同余方程组：

$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{n}_1)\\ x\equiv a_2(\mathrm{mod}{n}_2)\\ ⋮\\ x\equiv a_k(\mathrm{mod}{n}_k)\end{array}$$

并且，这个解 $x$ 在模 $N=n_1{n}_2\dots n_k$ 下是唯一的。

证明

1. 存在性：

• 由于 $n_1,n_2,\dots ,n_k$ 两两互质，$N=n_1{n}_2\dots n_k$。
• 对于每个 $i$，计算 $N_i=N/n_i$。由于 $n_i$ 与 $N_i$ 互质，存在整数 $m_i$ 使得 $m_i{N}_i\equiv 1(\mathrm{mod}{n}_i)$。
• 令 $x={\sum }_{i=1}^k{a}_i{m}_i{N}_i$。对于每个 $i$，$x\equiv a_i{m}_i{N}_i\equiv a_i\cdot 1\equiv a_i(\mathrm{mod}{n}_i)$，因此 $x$ 是方程组的解。

2. 唯一性：

• 假设 $x$ 和 $y$ 都是方程组的解，则 $x\equiv y(\mathrm{mod}{n}_i)$ 对所有 $i$ 成立。
• 由于 $n_i$ 两两互质，$x\equiv y(\mathrm{mod}N)$，即 $x$ 和 $y$ 在模 $N$ 下相同。

中国剩余定理通过将大模数问题分解为小模数问题，简化了计算过程。

实现

扩展欧几里得算法求逆元

乘法逆元是数论中的一个重要概念。给定整数 $a$ 和模数 $m$，如果存在整数 $x$ 使得 $ax\equiv 1(\mathrm{mod}m)$，则称 $x$ 是 $a$ 在模 $m$ 下的乘法逆元，记作 $a^{-1}$。

1. 使用欧几里得算法求 $\gcd (a,m)$。
2. 如果 $\gcd (a,m)\ne 1$，则 $a$ 在模 $m$ 下没有逆元。
3. 如果 $\gcd (a,m)=1$，则通过扩展欧几里得算法求出 $x$ 和 $y$，使得：

$$ax+my=1$$

此时，$x$ 就是 $a$ 在模 $m$ 下的逆元。

代码

void exgcd(int a,int b,int &X,int &Y){
   
	if(!b){
   X=1,Y=0;return ;}
	exgcd(b,a%b,X,Y);
	int t=X;
	X=Y;
	Y=t-a/b*X;
}

完整代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n,m[11],r[11],c,M=1,x,y,ans;

void exgcd(int a,int b,int &X,int &Y){
   
	if(!b){
   X=1,Y=0;return ;}
	exgcd(b,a%b,X,Y);
	int t=X;
	X=Y;
	Y=t-a/b*X;
}

signed main(){
   
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
   
		scanf("%lld%lld",&m[i],&r[i]);
		M*=m[i];
	}
	for(int i=1;i<=n;i++){
   
		c=M/m[i];
		exgcd(c,m[i],x,y);
		ans=((ans+c*x*r[i])%M+M)%M;
	}
	printf("%lld",ans);
	return 0;
}