中国剩余定理（CRT）

数学

作业部落

评论地址

---

一、对于一系列同余方程的求解

$$\begin{cases} x\equiv a_1 \quad(mod \quad p_1) \\ x\equiv a_2 \quad (mod \quad p_2)\\...\\x\equiv a_n \quad (mod \quad p_n) \end{cases}$$
先考虑两项的情况 $$\begin{cases} x\equiv a_1 \quad(mod \quad p_1) \\ x\equiv a_2 \quad (mod \quad p_2)\end{cases}$$ 先假设$gcd(p_1,p_2)=1$
令$x_0$为其一解，则有 $$x_0=a_1+k_1*p_1=a_2+k_2*p_2$$ 那么会有方程$p_1*k_1-p_2*k_2=a_2-a_1$
运用扩展欧几里得求得一解$(k_1',k_2')$
则可以得$x_0$以及$k_1=k_1'+p_2*t$
$x=a_1+k_1*p_1=a_1+k_1'*p_1+t*p_1*p_2=x_0+t*p_1*p_2$
即$x\equiv x_0\quad(mod \quad p_1p_2)$
将$n$个依次合并可得结果

可以看作$x$加上$p_1p_2$对式子没有影响，那么$gcd(p_1,p_2)!=1$的时候就加$lcm(p_1,p_2)$（最小公倍数）就好了
最终$x\equiv x_0(mod \quad lcm(p_1,p_2...p_n))$

二、举例

孙子算经：今有物不知其数，三三数之余二，无物数之余三，七七数之余二，问物几何？

$$\begin{cases} x\equiv 2(mod \quad 3) \\ x\equiv 3(mod \quad 5)\\ x\equiv2(mod\quad 7)\end{cases}$$
由前两式列得方程$2+3k_1=3+5k_2$得$k_1'=2,k_2'=1,x_0=8$
$$\begin{cases} x\equiv 8(mod \quad 15) \\ x\equiv 2 (mod \quad 7)\end{cases}$$
列得方程$8+15k_1=2+7k_2$得$k_1'=1,k_2'=3,x_0=23$
$x\equiv 23(mod \quad 105)$从而得出$x=105k+23(k>=0)$
例题：韩信点兵

三、用途

可以处理这种同余方程
也可以处理任意模数NTT

Code

注意我的代码和网上绝大部分博主的不一样
大部分人是把同余方程拆开，像数学一本通上面做的那样
而我的就是在模拟上面说的过程
其中调试了很久，原因在于我的乘法可能会乘爆$long\ long$
加上$mul$函数就好啦（我也不知道为什么，哪位dalao可以告诉我原理>_<）

//COGS1786 韩信点兵
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
ll N,m,P[11],a[11];
ll mul(ll x,ll y,ll m)
{
    x%=m;y%=m;
    return (x*y-(ll)((long double)x/m*y+0.5)*m+m)%m;
}
void Exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){x=a;y=0;return;}
    Exgcd(b,a%b,y,x);y-=a/b*x;
}
void CRT()
{
    ll x,y,c;
    for(int i=2;i<=m;i++)
    {
        Exgcd(P[i-1],-P[i],x,y);
        c=a[i]-a[i-1];
        P[i]=P[i-1]*P[i];
        a[i]=((a[i-1]+mul(mul(x,c,P[i]),P[i-1],P[i]))%P[i]+P[i])%P[i];
    }
    while(a[m]+P[m]<=N) a[m]+=P[m];
    if(a[m]>N) puts("-1");
    else printf("%lld\n",N-a[m]);
}
int main()
{
    freopen("HanXin.in","r",stdin);
    freopen("HanXin.out","w",stdout);
    cin>>N>>m;
    for(int i=1;i<=m;i++)
        cin>>P[i]>>a[i];
    CRT();
}