中国剩余定理

原理

见《进阶指南》第154页。

模板题

洛谷-P1495-曹冲养猪

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 20;
LL a[N], m[N], prod_m = 1, M[N];

LL exgcd (LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, x, y);
    LL copy_x = x, copy_y = y;
    x = copy_y, y = copy_x - copy_y * (a / b);
    return d;
}

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lld%lld", &m[i], &a[i]);

    for (int i = 1; i <= n; ++ i) prod_m *= m[i];
    for (int i = 1; i <= n; ++ i) M[i] = prod_m / m[i];
    LL res = 0;
    for (int i = 1; i <= n; ++ i) {
        LL x = 0, y = 0;
        exgcd(M[i], m[i], x, y);
        res = (res + a[i] * M[i] % prod_m * x % prod_m) % prod_m;
    }
    res = (res % prod_m + prod_m) % prod_m;
    printf("%lld", res);
    return 0;
}