扩展中国剩余定理详解

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}$$

但是有一个非常令人不爽的事情就是它要求$m_1,m_2/ldots,m_r$两两互素

如果某个毒瘤出题人偏要求它们部互素呢?

其实也有解决的办法

就是把出题人吊起来干一顿用扩展中国剩余定理

扩展中国剩余定理跟中国剩余定理没半毛钱关系,一个是用扩展欧几里得,一个是用构造

首先我们还是从简单入手,考虑一下如果同余方程组只有两个式子的情况

$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}$

我们用$(a,b)$表示$a,b$的最大公约数

在这里需要注意,这个方程有解的条件是

$/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) }$这一项,如果不整除的话肯定会出现小数。

对于上面的方程,两边同除$(m_1,m_2)$

$$/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_2$消去了。

同余式两边同除$/dfrac {m_{1}}{/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$$

接下来怎么办呢?这个式子已经化到最简了。。

不要忘了,我们刚开始还有两个式子。我们把$k_1$待回去!

$$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)}}$$

此时,整个式子中的元素我们都已经知道了

具体一点,这个式子可以看做是$$x/equiv c/pmod m$$

其中$$c=(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)}*m_1+c_1$$

$$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

题解

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台