给定同余方程组,其中 mim_i两两互质

{xa1(modm1)xb2(modm2)xcn(modmn)\begin{cases} x≡a_1 (mod m_1) \\ x≡b_2 (mod m_2) \\ \cdots \\ x≡c_n (mod m_n) \end{cases}



我们尝试构造出一个式子,使得式子满足上列同余方程组

  1. M=mim2mn=inmiM = m_i \cdot m_2 \cdot \cdots \cdot m_n = \prod_i^n m_i
  2. Mi=M/miM_i = M / m_i
  3. ti=Mi1,Miti=1(modmi)t_i = M_i^{-1} , M_i t_i = 1 \pmod{m_i}
  • 则,方程的一组通解:

x=a1t1M1+a2t2M2++antnMn+kM=i=1naitiMi+kMx = a_1t_1M_1 + a_2t_2M_2 + \cdots +a_nt_nM_n + kM = \sum_{i=1}^n a_it_iM_i + kM

  • 证明
    根据22,我们可以得到 i!=j,Miti=0(modmi)i!=j,M_it_i = 0 \pmod{m_i}
    根据33,我们可以得到 i=j,Miti=ai(modmi)i=j,M_it_i = a_i \pmod{m_i}
    很显然,它的循环节为MM

  • 于是我们可以的得出,对于任意ii, x=ai(modmi)x = a_i \pmod{m_i}

int CRT(int a[], int m[], int n) {
    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 Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        ans = (ans + Mi * x * a[i]) % M;
    }
    if(ans < 0) ans += M;
    return ans;
}

---

为了得到tit_i,根据裴蜀定理,我们必须满足gcd(mi,Mi)=1gcd(m_i,M_i) =1 ,但如果mim_i不互质,则会出现不存在tit_i的情况

我们考虑当前仅存在两个方程

{xa1(modm1)xb2(modm2)\begin{cases} x≡a_1 (mod m_1) \\ x≡b_2 (mod m_2) \end{cases}

将其转换成不定方程

x=mip+a1=m2q+a2x = m_i p + a_1 = m_2 q + a_2

m1pm2q=a2a1m_1p - m_2q = a_2 - a_1

如果 a2a1gcd(m1,m2)a_2 - a_1 | gcd(m_1,m_2) ,则可通过扩展欧几里得,得到一组可行解(p,q)(p,q)
则两原方程的组成的新方程组解为 x=m1p(modlcm(m1,m2))x = m_1p \pmod {lcm(m_1,m_2)}

否则由裴蜀定理得知等式无解

long long crt(long long n) {
    long long M = b[1], ans = a[1], x, y;
    for (int i = 2; i <= n; i++) {
        long long z = (a[i] - ans%b[i]+b[i])%b[i];
        long long k = exgcd(M, b[i], x, y);
        if (z % k)
            return -1;
        long long c = b[i] / k;   
        x = mul(x,z/k,c);
        ans += x * M;  
        M = M * c;
        ans = (ans%M+M)%M;
    }
    return (ans % M + M) % M;
}