题解：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
zhangjizhi
·
·
题解
CRT 模板当然要用 CRT 了。（bushi）
简单介绍 CRT（源自 oiwiki）：
定义
中国剩余定理（Chinese Remainder Theorem，CRT）可求解如下形式的一元线性同余方程组（其中 n_1,n_2, \dotsi ,n_k 两两互质）：
x \equiv a_1 (mod\ n_1)\\
x \equiv a_2 (mod\ n_2)\\
\quad \vdots\\
x \equiv a_k (mod\ n_k)
\end{cases}
过程
（该部分与 oiwiki 上的过程略有不一样，出自我们机房的 XXh神犇）
设 M=\prod_{i=1}^k n_i，m_i=\frac{M}{n_i}，t_i 为 m_i 在模 n_i 意义下的逆元 m_i^{-1}，
## 证明
我们需要证明上面算法计算所得的 $x$ 对于任意 $i=1,2,\dotsi,k$ 满足 $x\equiv a_i\ (mod\ n_i)$。
当 $i\not =j$ 时，有 $m_j\equiv0\ (mod\ n_i)$，故 $c_j\equiv m_j\equiv 0\ (mod\ n_i)$。又有 $c_i\equiv m_i\cdot(t_i\ mod\ n_i) \equiv 1\ (mod\ n_i)$，所以有：
$$
\begin{aligned}
x&\equiv\sum_{j=1}^k a_jc_j&\qquad (mod\ n_i)\\
&\equiv a_ic_i&\qquad (mod\ n_i)\\
&\equiv a_i\cdot m_i\cdot(t_i\ mod\ n_i)&\qquad (mod\ n_i)\\
&\equiv a_i&\qquad (mod\ n_i)
\end{aligned}
$$
证毕。
## 代码实现
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int qcheng(int a,int b,int mod)
{
int ans=0;
a%=mod;
b%=mod;
while(b)
{
if(b&1) ans=(ans+a)%mod;
b>>=1;
a=(a+a)%mod;
}
return ans;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-(a/b)*y;
return d;
}
int k,a[100001],n[100001],x,y,m,M,t[100001],sum;
signed main()
{
cin>>k;
m=1;
for(int i=1;i<=k;i++)
{
cin>>a[i]>>n[i];
m*=a[i];
}
for(int i=1;i<=k;i++)
{
M=m/a[i];
int shu=exgcd(M,a[i],x,y);\\求逆元
x=(x%a[i]+a[i])%a[i];
sum=(sum+(qcheng(qcheng(M,x,m),n[i],m)%m+m))%m;\\慢乘防溢出
}
cout<<sum;
return 0;
}
```
做完后可尝试 [P4777EXCRT](https://www.luogu.com.cn/problem/P4777)。