「中国剩余定理CRT」学习笔记

设正整数$m_1, m_2, ... , m_r$两两互素，对于同余方程组

$x ≡ a_1 (mod m_1)$

$x ≡ a_2 (mod m_2)$

            $...$

$x ≡ a_r (mod m_r)$

有整数解。设$P = prodlimits_{k = 1}^{r} m_k$，则有

$$x ≡ a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ... + a_r M_r M_r^{-1} ( mod P)$$

其中，$M_i = frac{P}{m_i}$，$M_i^{-1}$为$M_i$在模$m_i$意义下的乘法逆元

 

证明：

对于每一个同余方程分开求解，设各个方程的解分别为$x_i$，则答案为$sumlimits_{i = 1}^{r}x_i$。

若对于$k≠i$，都有$m_k|x_i$，则最终累积答案的时候对当前同余方程产生影响的只有$x_i$

因此$x_i$应当为$frac{P}{m_i}$的倍数，且满足$x_i ≡ a_i (mod m_i)$

由于$M_i = frac{P}{m_i}$，因此求出$M_i$在模$m_i$意义下的逆元$M_i^{-1}$，可得$M_i M_i^{-1} ≡ 1 (mod m_i)$

同时乘以$a_i$即可得$a_i M_i M_i^{-1} ≡ a_i (mod m_i)$

由于$x_i ≡ a_i M_i M_i^{-1}  (mod m_i)$

所以$x = a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ... + a_r M_r M_r^{-1}$

若要求x的最小正整数值，$mod P$即可：$x ≡ a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ... + a_r M_r M_r^{-1} ( mod P)$

 

代码实现

/*By DennyQi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define  r  read()
using namespace std;
inline int read(){
    int x = 0; int w = 1; register int c = getchar();
    while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w;
}
int K,P=1,x,y;
int a[15],b[15];
void exgcd(int M, int B){
    if(!B){
        x = 1, y = 0;
        return;
    }
    exgcd(B, M%B);
    int tmp = x;
    x = y;
    y = tmp - (M / B) * y;
}
int GetInv(int M, int B){
    exgcd(M, B);
    return (x + B) % B;
}
inline void CRT(){
    int M,inv,ans=0;
    for(int i = 1; i <= K; ++i){
        M = P / b[i];
        inv = GetInv(M, b[i]);
        ans = (ans + a[i]*M*inv) % P;
    }
    printf("%d", ans);
}
int main(){
    K = r;
    for(int i = 1; i <= K; ++i) a[i] = r;
    for(int i = 1; i <= K; ++i) b[i] = r, P *= b[i];
    CRT();
    return 0;
}