扩展中国剩余定理详解
前言
阅读本文前,推荐先学一下中国剩余定理。其实不学也无所谓,毕竟两者没啥关系
扩展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
上一篇: Python3 微信