中国剩余定理 get ！

· · 个人记录

中国剩余定理：

原文链接1

原文链接2

现有如下同余方程组：

（m 互质）

求解 x 的最小值。

过程如下:

设：

k_1 ≡ 1\ (\%\ m_1) k_2 ≡ 1\ (\%\ m_2) k_3 ≡ 1\ (\%\ m_3) x = a_1 \times k_1 + a_2 \times k_2 + a_3 \times k_3

所以：

(a_2 \times k_2 + a_3 \times k_3) \% m_1 = 0 (a_1 \times k_1 + a_3 \times k_3) \% m_2 = 0 (a_1 \times k_1 + a_2 \times k_2) \% m_3 = 0

所以要先求出公倍数，再依次求 k ，由于开始时的 k 不是最终结果，所以结果要乘系数 x

int CRT()
{  
    int M = 1;  
    int ans = 0;  
    for(int i=1; i<=n; i++) M *= m[i];
    for(int i=1; i<=n; i++)
    {
        int x,y;
        int k = M / m[i];
        Exgcd(k,m[i],x,y);
        k = (k*x)%M;
        ans = (ans+k*a[i])%M;  
    }  
    ans = (ans+M)%M; 
    return ans;  
}

扩展中国剩余定理：

与朴素定理的区别就是 m 不互质

思路是从前两项开始合并，找出前两个方程的通解，再与第三项合并

设：

x = k_1 \times m_1 + a_1 x = k_2 \times m_2 + a_2 A = a_2 - a_1

∴ k_1 \times m_1 + k_2 \times m_2 = A

k_1 = k_2 \times \dfrac A{\gcd(m_1,m_2)}

将 k_1 回代：

( X 表示 x 的一个通解，目的就是将它不断传递）

X = k_1 \times m_1 + a_1 X ≡ x (\%\ lcm(m_1,m_2))

所以：

m_2 = lcm(m_1,m_2) a_2 = X

传送门

LL m[MAXN],a[MAXN];

LL FastMul(LL a, LL x, LL p)
{
    LL ans=0;
    while(x)
    {
        if(x & 1)   ans = (ans+a) % p;
        a = (a+a) % p; 
        x >>= 1;
    }
    return ans;
}

int ExGCD(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;  y = 0;
        return a;
    }
    LL g = ExGCD(b,a%b,y,x);
    y -= (a/b)*x;
    return g;
}

void ExCRT()
{
    for(int i=2;i<=n;i++)
    {
        LL k,y;
        LL m1 = m[i-1];
        LL m2 = m[i];
        LL A = a[i]-a[i-1];
        LL g = ExGCD(m1,m2,k,y);
        LL p = m2/g;
        k = (k%p+p) % p;    //保证 k 为正 
        A = ((A/g)%p+p) % p;//保证 A 为正 
        k = FastMul(k,A,p) % p;//求 k 
        m[i] = m1*p;    //lcm 
        a[i] = m1*k+a[i-1]; 
    }
}

int main(void)
{
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> m[i] >> a[i];
    ExCRT();
    cout << a[n];
    return 0;
}