中国剩余定理

概念讲解

什么是中国剩余定理？

中国剩余定理（CRT）用于求解同余方程组。

问题

求解：
x≡a1(modm1)x \equiv a_1 \pmod{m_1}
x≡a2(modm2)x \equiv a_2 \pmod{m_2}
......
x≡an(modmn)x \equiv a_n \pmod{m_n}

条件

m_1, m_2, ..., m_n 两两互质。

实现

基本 CRT

1234567891011121314int crt(vector<int>& a, vector<int>& m) {
    int n = a.size();
    int M = 1;
    for (int i = 0; i < n; i++) M *= m[i];
    
    int result = 0;
    for (int i = 0; i < n; i++) {
        int Mi = M / m[i];
        int xi = extgcd(Mi, m[i]).first;
        result = (result + a[i] * Mi * xi) % M;
    }
    
    return (result + M) % M;
}

扩展 CRT

用于 m 不两两互质的情况。

12345678910111213141516171819202122long long excrt(vector<long long>& a, vector<long long>& m) {
    int n = a.size();
    long long M = m[0];
    long long result = a[0];
    
    for (int i = 1; i < n; i++) {
        long long d = gcd(M, m[i]);
        long long c = a[i] - result;
        
        if (c % d != 0) return -1;
        
        long long x, y;
        extgcd(M / d, m[i] / d, x, y);
        
        x = (x * (c / d)) % (m[i] / d);
        result += x * M;
        M = M / d * m[i];
        result = (result % M + M) % M;
    }
    
    return result;
}

考点分析

初赛考查方式

  1. 选择题： CRT 的概念
  2. 程序阅读： 理解 CRT
  3. 编程题： CRT 应用

常见题型

  • 同余方程组
  • 扩展 CRT

例题精讲

例题 1：CRT

题目： 求解同余方程组。

解答：

1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>
#include <vector>
using namespace std;

long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n), m(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> m[i];
    }
    
    long long M = 1;
    for (int i = 0; i < n; i++) M *= m[i];
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];
        long long x, y;
        extgcd(Mi, m[i], x, y);
        result = (result + a[i] * Mi * x) % M;
    }
    
    cout << (result + M) % M << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1495 CRT
查看答案

思路：中国剩余定理模板题。

123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>
#include <vector>
using namespace std;

long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n), m(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> m[i];
    
    long long M = 1;
    for (int i = 0; i < n; i++) M *= m[i];
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];
        long long x, y;
        extgcd(Mi, m[i], x, y);
        result = (result + a[i] * Mi * x) % M;
    }
    
    cout << (result + M) % M << endl;
    return 0;
}
  1. 洛谷 P4777 EXCRT
查看答案

思路：扩展中国剩余定理，处理模数不互质的情况。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>
#include <vector>
using namespace std;

long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n), m(n);
    for (int i = 0; i < n; i++) cin >> m[i] >> a[i];
    
    long long M = m[0];
    long long result = a[0];
    
    for (int i = 1; i < n; i++) {
        long long d = __gcd(M, m[i]);
        long long c = a[i] - result;
        
        if (c % d != 0) {
            cout << -1 << endl;
            return 0;
        }
        
        long long x, y;
        extgcd(M / d, m[i] / d, x, y);
        
        x = (x * (c / d)) % (m[i] / d);
        result += x * M;
        M = M / d * m[i];
        result = (result % M + M) % M;
    }
    
    cout << result << endl;
    return 0;
}
  1. 洛谷 P3868 猜数
查看答案

思路：扩展中国剩余定理。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>
#include <vector>
using namespace std;

long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

int main() {
    int k;
    cin >> k;
    
    vector<long long> a(k), m(k);
    for (int i = 0; i < k; i++) cin >> a[i];
    for (int i = 0; i < k; i++) cin >> m[i];
    
    // 处理负数
    for (int i = 0; i < k; i++) {
        a[i] = (a[i] % m[i] + m[i]) % m[i];
    }
    
    long long M = m[0];
    long long result = a[0];
    
    for (int i = 1; i < k; i++) {
        long long d = __gcd(M, m[i]);
        long long c = a[i] - result;
        
        if (c % d != 0) {
            cout << -1 << endl;
            return 0;
        }
        
        long long x, y;
        extgcd(M / d, m[i] / d, x, y);
        
        x = (x * (c / d)) % (m[i] / d);
        result += x * M;
        M = M / d * m[i];
        result = (result % M + M) % M;
    }
    
    cout << result << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. CRT 要求模数两两互质
  2. 扩展 CRT 可以处理模数不互质的情况
  3. 注意溢出问题
  4. CRT 是数论的重要定理