一、CRT
1. 前置芝士
- exgcd
2. 应用范围
求解同余方程组：
\[\begin{cases}x\equiv a_1\mod m_1\\x\equiv a_2\mod m_2\\x\equiv a_3\mod m_3\\~~~~~~~~~~~~~\vdots\\x\equiv a_k\mod m_k\end{cases} \]其中 \(~m_1,m_2,m_3,\cdots,m_k~\) 两两互质
3. 算法原理
考虑构造一组解：
记\(~M = \prod\limits_{i = 1} ^k m_i~\)，\(~M_i = \frac M {m_i}~\)，\(~t_i = {M_i}^{-1} \mod m_i~\)
那么我们可以构造一个解：
\[x = \sum\limits_{i = 1}^{k} a_i\times M_i \times t_i \]为什么是对的呢?
我们考虑对第\(~j~\)个同余方程：
除了\(~M_j~\)，其他的\(~M_i~\)都有\(~m_j~\)这个因子，即可得到
\[(x = \sum\limits_{i = 1}^{k} a_i\times M_i \times t_i)\equiv a_j\times M_j\times t_j\mod m_j \]又因为\(~M_j\times t_j \equiv 1 \mod m_j~\)
\[x \equiv a_j\times M_j\times t_j\equiv a_j \mod m_j \]4. 代码实现
const int NN = 1e5 + 8;
int k;
int a[NN],m[NN];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b == 0){return x = 1,y = 0,a;}
exgcd(b,a%b,x,y);
ll z = x;
x = y;
y = z - y * (a / b);
}
ll inv(ll a,ll mod){
ll x = 0,y = 0;
exgcd(a,mod,x,y);
return (x % mod + mod) % mod;
}//exgcd求逆元
int main(){
scanf("%d",&k);
ll M = 1;
for(int i = 1; i <= k; ++i) scanf("%d%d",&m[i],&a[i]),M *= m[i];
ll ans = 0;
for(int i = 1; i <= k; ++i){
ll Mi = M / m[i],invMi = inv(Mi,m[i]);
ans += a[i] * Mi * invMi;
}
printf("%lld",ans % M);
}
二、exCRT
咕咕咕
标签：CRT,int,ll,exgcd,times,exCRT,mod,equiv From： https://www.cnblogs.com/rickylin/p/17766055.html