姓名： 石润禾
赛道： 提高组
类型： 算法技能
中国剩余定理（CRT）
关键词： 数论、中国剩余定理、CRT
前置知识：逆元，同余，扩展欧几里得定理
-
引入：
如何找到一个最小的数，使得这个数除以3余2，除以5余3，除以7余2？
使用CRT的解法如下：1.找到三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1的最 小数21，最后从5和7的公倍数中找出除3余1的最小数70。
2.将15乘2(被7除的余数)=30，21乘3(被5除的余数)=63，70乘2(被3除的余数)=140，
3.把上面的3个数相加，即30+63+140=233，让233对3,5,7的最小公倍数105取模，得到23，23即为答案 -
定义：
中国剩余定理可以求解以下形式的一元线性同余方程组：\begin{cases} x ≡ a_1\,(mod\;n_1)\newline x ≡ a_2\,(mod\;n_2)\newline ...\newline x ≡ a_k\,(mod\;n_k) \end{cases}具体过程：
1.计算所有模数的积 n
2.对于第 i 个方程，
(1) 计算 m_i=\frac{n}{n_i}
(2) 计算 m_i 在模 n 意义下的逆元（ m_i^{-1}(mod\;n) ）
(3) 计算 c_i=m_i·m_i^{-1}
3.此方程组在 mod\:n 意义下的唯一解为 \sum\limits^k_{i=1}a_ic_i(mod\:n) -
证明：
(证明 x 满足对于任意 i=1,2,...k ,都有 x≡a_i(mod\;n_i) )
当 i≠j 时，一定有 m_j≡0(mod\;n_i) ,所以 c_j≡m_j≡0(mod\;n_i)
又有 c_i≡m_i·(m_i^{-1}\;mod\;n_i)≡1(mod\;n_i)
所以我们得出：
\;\;\;\sum\limits^k_{j=1}a_jc_j\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(mod\;n_i)
≡a_ic_i\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(mod\;n_i)
≡a_i·m_i·m_i^{-1}\;mod\;n_i\;\;\;(mod\;n_i)
≡a_i\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(mod\;n_i)
即：对于任意的 i=1,2,...k ,上面算法得出的 x 都满足 x≡a_i(mod\;n_i) ,证明上面算法正确。 -
实现：
long long crt(int k) { long long n=1,ans=0; for (int i=1;i<=k;i++) n=n*r[i];//计算所有模数的积 for (int i=1;i<=k;i++) { long long m=n/r[i],b,y; exgcd(m,r[i],b,y);//b*m mod r[i]=1(求逆元) ans=(ans+a[i]*m*b%n)%n; } return (ans%n+n)%n; }
下面给一道例题吧~
我们设两只青蛙跳了t次后碰面，
则此时青蛙A的坐标为x+mt，青蛙B的坐标为y+nt，由题意得
x+mt-(y+nt)=Lp（p为整数）
附上本人的代码：
#include<bits/stdc++.h>
using namespace std;
long long xx,yy,g;
long long n,m,x,y,l;
void exgcd(long long a,long long b)
{
if(!b)
{
xx=1;
g=a;
return;
}
exgcd(b,a%b);
long long num=xx;
xx=yy;
yy=num-a/b*yy;
}
int main()
{
while(cin >> x >> y >> m >> n >> l)
{
long long num1=n-m,num2=x-y;
if(num1<0) num1=-num1,num2=-num2;
exgcd(num1,l);
if(num2%g!=0) cout << "Impossible\n";
else
{
long long tmp=l/g;
long long ans=(num2/g*xx%tmp+tmp)%tmp;
cout << ans << "\n";
}
}
return 0;
}
好啦，我的讲解到此结束了，本人是蒟蒻，若有不足请多多指教哦！ 
点个赞呗~ 
