Poj 2891

题解

中国剩余定理扩展模板题

/*
x = m1 * x1 + a1 = m2 * x2 + a2
=> m1 * x1 + a1 = m2 * x2 + a2
=> m1 * x1 + m2 * x2 = a2 - a1
gcd(m1, m2) | a2 - a1
x0 为方程
m1 * x1 + m2 * x2 = gcd(m1, m2) 的特解
x0 *= [(a2 - a1) / gcd(m1, m2)]
x0 为方程
m1 * x1 + m2 * x2 = a2 - a1 的一组解
x0 + m2 / gcd * t 化为最小
将 x0 回带 x' = a1 + m1 * x1
显然 x 的通解为 x' + lcm(m1, m2)t, 才能保证 x % m1, m2 的余数分别为 a1, a2.
相当于 x = x' (mod lcm(m1, m2))
然后与第三个方程继续进行合并
*/
#include <iostream>
#include <cstdio>
const int N = 1e5 + 10;
#define LL long long
LL m[N], a[N], n;
LL Exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {x = 1, y = 0; return a;}
    int ret = Exgcd(b, a % b, x, y);
    int tmp = x; x = y, y = tmp - a / b * y;
    return ret;
}
inline LL Work() {
    LL M = m[1], A = a[1], x, y;
    for(int i = 2; i <= n; i ++) {
        LL d = Exgcd(M, m[i], x, y);
        if((a[i] - A) % d) return -1;
        x *= ((a[i] - A) / d);
        LL t = m[i] / d;
        x = ((x % t) + t) % t;
        A = A + M * x; M = M / d * m[i];
        A %= M;
    }
    A = (A % M + M) % M;
    return A;
}
int main() {
    while(std:: cin >> n) {
        for(int i = 1; i <= n; i ++) std:: cin >> m[i] >> a[i];
        std:: cout << Work() << "\n";
    }
    return 0;
}