同余复习笔记？

扩展欧几里得

用于在 (a) , (b) 已知的情况下求出一组 (x) , (y) 的任意解满足: ax+by=c

根据裴蜀定理，此方程有解的充要条件为 (gcd(a,b)|c)

于是我们可以将 ax+by=c 简化为 ax+by=gcd(a,b) 前面方程的解不过是后面方程的解扩大整数倍。

求解过程：

[\ ax+by=gcd(a,b) \ gcd(a,b)=gcd(b,a\%b) \ 可以得出：bx'+(a\%b)∗y'=gcd(b,a\%b) \ 又因为:a\%b = a-lfloor frac{a}{b} floor *b \ 所以：a*y'+b*(x'-lfloor frac{a}{b} floor*y') = gcd(a,b) \ 所以原方程中的一组任意解为： egin{cases} x=y' \ y=x'-lfloor frac{a}{b} floor *y' end{cases} ]

递归求解即可

inline void Exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1;y=0;return;}//其实这个时候y可以为任意数。(因为y前的系数b=0)
    Exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
    return;
}

扩展欧几里得求逆元

即 (a*inv[a]=1 (mod m))

用扩展欧几里得求逆元的前提是 (a,m) 互质

原方程可以化简为：

(a*inv[a] + my = 1)

因为 (a,m) 互质，所以原式可以变为：

(a*inv[a] + my = gcd(a,m))

就是上面的式子。

注意，此时求出的逆元很有可能为负，需要 (x+m)%m 强制变为正。

为什么此时求出的就是逆元呢？

移项一下：

(a*inv[a] = 1-my)

即 (a*inv[a] = 1(mod m))

得证。

中国剩余定理：(CRT)

求解形如

[egin{cases} x equiv a_1 (mod m_1) \ x equiv a_2 (mod m_2) \ x equiv a_3 (mod m_3) \ ... \ ... \ x equiv a_k (mod m_k) \ end{cases} ]

其中 (m_i) 互质，求出最小的满足上述条件的 (x)

令一个 (M=prod _{i=1} ^{k} m_i M_i=frac{M}{m_i})

(t_i) 为 (M_i) 在 (mod m_i) 意义下的逆元，即(M_i*t_iequiv1(mod m_i))

所以 (M_i) 与 (m_i) 也互质。

那么：一个解 (ans = Sigma_{i=1}^{k} (a_i*M_i*t_i))

证明：

对于任意的 (j eq i)

(m_i | M_j) 所以 (a_j*M_j*t_j =0(mod m_i))

而因为 (M_i*t_i equiv 1(mod m_i))

所以 (a_i*M_i*t_i=a_i(mod m_i))

对于任意的 (i) 上述证明都是成立的，由此当前得到的解 (ans) 是满足上面的式子的。

而最小解则为 (ans \% M)

(上面有很多步，不同步的模数是不同的，比如 (t_i) 是 (m_i) 在 (mod m_i) 意义下的逆元，而最后需要 (\%) 的是 (M))

inline void Exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return;}
    Exgcd(b,a%b,x,y);
    ll z=x;x=y,y=z-y*(a/b);
    return;
}
int n;
ll a[N],m[N],M[N],mul=1,inv[N],tmp,ans;
int main(){
    read(n);
    for(register int i=1;i<=n;++i)  read(m[i]),read(a[i]),mul*=m[i];
    for(register int i=1;i<=n;++i){
        tmp=0;M[i]=mul/m[i];Exgcd(M[i],m[i],inv[i],tmp);
        inv[i]=(inv[i]+m[i])%m[i];//此时的inv是在%m[i]意义下的，所以强制为正+的也为m[i]
        ans+=((a[i]*inv[i])%mul*M[i])%mul;//其实可以不加这里的取模的根据上面推的式子。
    }
    print(ans%mul);
    return 0;
}

持续咕咕咕。