同余方程&孙子定理&模线性同余方程

参考博客

Acdreamer

一次同余方程

1. 若有 (a,n)=1 $(a,n)=1$,根据 欧几里得扩展，存在 l,m使得 a∗l+n∗m=1 $a\ast l+n\ast m=1$，等式两边同时模n，得 a∗l≡1(mod n) $a\ast l\equiv 1\left(modn\right)$,对于
   a∗x≡b(mod n) $a\ast x\equiv b\left(modn\right)$
   a∗l∗x≡b∗l(mod n) $a\ast l\ast x\equiv b\ast l\left(modn\right)$
   x≡b∗l(mod n) $x\equiv b\ast l\left(modn\right)$

1. 若有 (a,n)=d $(a,n)=d$, 对于
   a∗x≡b(mod n) $a\ast x\equiv b\left(modn\right)$

移项

中国剩余定理

解线性同余方程，运用拉格朗日插值法，得孙子定理

模板

int m[maxn];
int  China(int a[],int n,int b[])//其中a[]是模数，b[] 是余数
{
    int M = 1;
    for(int i = 0;i < n;++i)
        M *= a[i];
    int ans = 0;
    for(int i = 0;i < n;++i)
    {
        int Mi = M/a[i];
        LL x,y;
        ex_gcd(Mi,a[i],x,y);
        ans += b[i] * x*Mi;
    }
    ans = (ans%M + M) %M;
    return ans;
}

扩展

合并两个模数
假设
          y=a1(mod m1) $y=a_1\left(mod{m}_1\right)$
         y=a2(mod m2) $y=a_2\left(mod{m}_2\right)$
令
         x≡a1+t1∗m1;（1） $x\equiv a_1+t_1\ast m_1;（1）$
         x≡a2+t2∗m2;（2） $x\equiv a_2+t_2\ast m_2;（2）$
两式相减得         t1∗m1−t2∗m2=a1−a2（3） $t_1\ast m_1-t_2\ast m_2=a_1-a_2（3）$
        利用欧几里得扩展求出 t1 $t_1$带入（1） 求出一个特解 x $x$