数论：中国剩余定理
mydcwfy
·
·
个人记录
中国剩余定理
0. 前置知识
逆元。
我的逆元 Blog
1. 处理的问题
求 $x\in \Z$，使：
$$
\left\{
\begin{array}{ll}
x=a_1\pmod {m_1}\\
x=a_2\pmod {m_2}\\
...\\
x=a_n\pmod {m_n}
\end{array}
\right.
$$
### 2. 解决的方法
设 $M=m_1m_2...m_n$。
令 $M_i=\dfrac{M}{m_i},t_i=M_i^{-1}\pmod {m_i}$。
那么，$x=\sum_{i=1}^{n}{a_i*t_i*M_i}$。
证明略。（背就行了 ~~逃~~）
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=12;
int n,m[N],b[N];
void exGCD(ll a,ll b,ll &x,ll &y)
{
if (!b)
{
x=1;y=0;
return;
}
exGCD(b,a%b,y,x);
y-=a/b*x;
return;
}
int main()
{
cin>>n;
for (int i=1;i<=n;++i)
scanf("%d %d",&m[i],&b[i]);
ll M=1,res=0;
for (int i=1;i<=n;++i) M*=m[i];
for (int i=1;i<=n;++i)
{
ll Mi=M/m[i],ti,x;
exGCD(Mi,m[i],ti,x);
res+=b[i]*Mi*ti;
}
printf("%lld\n",(res%M+M)%M);
return 0;
}
```