# 扩展中国剩余定理详解

2018-02-07 20:14:45来源:cnblogs.com作者:自为风月马前卒人点击

## 扩展CRT

\$\$/begin{cases}x/equiv c_{1}/left( mod/ m_{1}/right) // x/equiv c_{2}/left( mod/ m_{2}/right) // /ldots // x/equiv c_r/left( mod/ m_r/right) /end{cases}\$\$

\$x/equiv c_{1}/left( mod/ m_{1}/right) // x/equiv c_{2}/left( mod/ m_{1}/right)\$

\$x=c_{1}+m_{1}k_{1}// x=c_{2}+m_{2}k_{2}\$

\$c_{1}+m_{1}k_{1}=c_{2}+m_{2}k_{2}\$

\$m_{1}k_{1}=c_{2}-c_{1}+m_{2}k_{2}\$

\$/left( m_{1},m_{2}/right) |/left( c_{2}-c_{1}/right)\$，因为后面会用到\$/dfrac {/left( c_{2}-c_{1}/right) }{/left( m_{2},m_{1}/right) }\$这一项，如果不整除的话肯定会出现小数。

\$\$/dfrac {m_{1}k_{1}}{/left( m_{1},m_{2}/right) }=/dfrac {c_{2}-c_{1}}{/left( m_{1},m_{2}/right) }+/dfrac {m_{2}k_{2}}{/left( m_{1},m_{2}/right) }\$\$

\$\$/dfrac {m_{1}}{/left( m_{1},m_{2}/right) }k_{1}=/dfrac {c_{2}-c_{1}}{/left( m_{1},m_{2}/right) }+/dfrac {m_{2}}{/left( m_{1},m_{2}/right) }k_{2}\$\$

\$\$/dfrac {m_{1}}{/left( m_{1},m_{2}/right) }k_{1} /equiv /dfrac {c_{2}-c_{1}}{/left( m_{1},m_{2}/right) } (mod/ /dfrac {m_{2}}{/left( m_{1},m_{2}/right) })\$\$

\$\$k_1/equiv inv({m_1/over(m_1,m_2)},{m_2/over (m_1,m_2)})*{(c_2-c_1)/over (m_1,m_2)}/pmod {{m_2/over(m_1,m_2)}}\$\$

\$inv(a,b)\$表示\$a\$在模\$b\$意义下的逆元

\$\$k_1=inv({m_1/over(m_1,m_2)},{m_2/over (m_1,m_2)})*{(c_2-c_1)/over (m_1,m_2)}+{{m_2/over (m_1,m_2)}}*y\$\$

\$\$x=inv({m_1/over(m_1,m_2)},{m_2/over (m_1,m_2)})*{(c_2-c_1)/over (m_1,m_2)}*m_1+y{{m_1m_2/over (m_1,m_2)}}+c_1\$\$

\$\$x/equiv inv({m_1/over(m_1,m_2)},{m_2/over (m_1,m_2)})*{(c_2-c_1)/over (m_1,m_2)}*m_1+c_1/pmod {{m_1m_2/over (m_1,m_2)}}\$\$

\$\$m={m_1m_2/over (m_1,m_2)}\$\$

## 代码

`#include<iostream>#include<cstdio>#define LL long long using namespace std;const LL MAXN=1e6+10;LL K,C[MAXN],M[MAXN],x,y;LL gcd(LL a,LL b){    return b==0?a:gcd(b,a%b);}LL exgcd(LL a,LL b,LL &x,LL &y){    if(b==0){x=1,y=0;return a;}    LL r=exgcd(b,a%b,x,y),tmp;    tmp=x;x=y;y=tmp-(a/b)*y;    return r;}LL inv(LL a,LL b){    LL r=exgcd(a,b,x,y);    while(x<0) x+=b;    return x;}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    while(~scanf("%lld",&K))    {        for(LL i=1;i<=K;i++) scanf("%lld%lld",&M[i],&C[i]);        bool flag=1;        for(LL i=2;i<=K;i++)        {            LL M1=M[i-1],M2=M[i],C2=C[i],C1=C[i-1],T=gcd(M1,M2);            if((C2-C1)%T!=0) {flag=0;break;}            M[i]=(M1*M2)/T;            C[i]= ( inv( M1/T , M2/T ) * (C2-C1)/T ) % (M2/T) * M1 + C1;            C[i]=(C[i]%M[i]+M[i])%M[i];        }        printf("%lld/n",flag?C[K]:-1);    }    return 0;}`

http://acm.hdu.edu.cn/showproblem.php?pid=1573