C12第2章中国剩余定理

admin

3
3 2
5 3
7 2

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
int a[101], m[101];
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;

}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m[i] >> a[i];
    }
    cout << CRT(a, m, n) << endl;

    return 0;
}