《算法竞赛进阶指南》表达整数的奇怪方式 · 同余

题解

这里不能直接用中国剩余定理的板子，因为没有说模数都是互质的

题解参考

感觉这个过程不是我一眼能记住的，参照大佬的博客，我再跟一遍过程



最后把n个式子合并成1个式子，也就是

所以最终的答案即 $m_0$m0​，
其中要注意推导的过程中可能会出现的问题，因为gcd可能是负的！！！

---

---

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, K;
ll a1, m1, a2, m2;

void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b, d, x, y);
        ll tmp = x;
        x = y;
        y = tmp - a / b * y;
    }
}

int main() {
    ios::sync_with_stdio(0);

    cin >> n;
    cin >> a1 >> m1;
    for (int i = 1; i < n; ++i) {
        cin >> a2 >> m2;
        ll d, x, y, k1;
        exgcd(a1, -a2, d, x, y);
        if ((m2 - m1) % (d)) return puts("-1"), 0;
        k1 = (x * ((m2 - m1) / d)% abs(a2 / d) + abs(a2 / d)) % abs(a2 / d);
        //务必小心这里 (x * ((m2 - m1) / d) 有可能是负的
        m1 = m1 + k1 * a1;
        a1 = abs(a1 / d * a2);
    }
    cout << m1 << endl;
    return 0;
}