P1495 【模板】中国剩余定理(CRT)/曹冲养猪

x=∑i=1nai×Mi×Mi−1(mod⁡ mi) mod⁡mx=\sum\limits_{i=1}^{n}a_i\times M_i\times M^{-1}_i(\operatorname{mod}~m_i)~\operatorname{mod}m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#define re register
#define int long long
const int MAXn = 10;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}

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

int inv(int n, int mod) {
    int ans, k;
    exgcd(n, mod, ans, k);
    return (ans % mod + mod) % mod;
}

int n, a[MAXn + 10], m[MAXn + 10];
int Crt() {
    int ans = 0, mulm = 1;
    for (re int i = 1; i <= n; ++i) {
        mulm = mulm * m[i];
    }
    for (re int i = 1; i <= n; ++i) {
        int M = mulm / m[i];
        ans = (ans + ((a[i] * M) % mulm * inv(M, m[i])) % mulm) % mulm;
    }
    return ans;
}

signed main() {
    read(n);
    for (re int i = 1; i <= n; ++i) {
        read(m[i]), read(a[i]);
    }
    printf("%lld\n", Crt());
}