首页 > 代码库 > [中国剩余定理]【学习笔记】

[中国剩余定理]【学习笔记】

2024-09-04 08:03:10   236人阅读

我会手写latex了哈哈哈O(∩_∩)O

终于会插入公式了，这样就可以去抄别人的公式啦

第一段直接抄zyf2000 第二段自己写的

求解同余方程请看 http://www.cnblogs.com/candy99/p/5765986.html

Chinese Remainder Theorem 中国剩余定理

求解同余方程组

$x\equiv a_1\pmod {m_1}\\ $
$x\equiv a_2\pmod {m_2} \\ $
$x\equiv a_3\pmod {m_3}\\$
$...\\$
$x\equiv a_n\pmod {m_n}$

其中 $ (m_i,m_j)=1,1<=i\neq j<=k $

直接构造解：

$ M=m_1*m_2*m_3*...*m_k $

$ x=(\sum\limits_{i=1}^k a_i*{M\over m_i}*inv({M\over m_i},mi))\%M $

证明：

x mod m[i]时 第i个式子因为有乘逆元所以结果是ai*1，其他的M可以整除m[i]所以都是0，方程组成立啊

 

ll m[N],a[N],M=1;void exgcd(ll a,ll b,ll &d,ll &x,ll &y){    if(b==0) d=a,x=1,y=0;    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;}ll Inv(ll a,ll p){    ll d,x,y;    exgcd(a,p,d,x,y);    return d==1?(x+p)%p:-1;}ll CRT(int n,ll *a,ll *m){    ll x=0;    for(int i=1;i<=n;i++){        ll w=M/m[i];        x=(x+a[i]*w%M*Inv(w,m[i]))%M;    }    return x;}

 

合并同余方程

如果不满足m两两互质，我们采用合并同余方程的方法将方程两两合并

两个方程可以写成$ x=m_1*t_1+a_1=m_2*t_2+a_2 $ 

变形  $ m_1*t_1-m_2*t_2=a_2-a_1 $

有解时$ gcd(m_1,m_2) | (a_2-a_1) $

$exgcd$解出$t_1$，当前是$mod \frac{m_2}{d}$意义下，找最小的$t_1$就行了

合并后方程为 $x\equiv a_1+t_1*m_1\pmod {lcm(m_1,m_2)}\\ $

 

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){    if(b==0) d=a,x=1,y=0;    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;}int main(){    freopen("in","r",stdin);    while(scanf("%lld",&n)!=EOF){        int flag=0;        m1=read();a1=read();n--;        while(n--){            m2=read();a2=read();            if(flag) continue;            ll d,t1,t2;            exgcd(m1,m2,d,t1,t2);            if((a2-a1)%d){flag=1;continue;}            t1*=(a2-a1)/d;            m2/=d;            t1=(t1%m2+m2)%m2;            a1=a1+m1*t1;            m1*=m2;        }        if(flag) puts("-1");        else printf("%lld\n",a1);    }}

 

[中国剩余定理]【学习笔记】


联系
我们