思路

嗯，我这种数学菜鸡来写数学题的确很难过。

首先分析题意，明显的就是提供一些线性同余方程，然后求解。但是，与中国剩余定理不同的是，这道题不保证模数互质。

\[ x \equiv a_1 (mod\ m_1) \\ x \equiv a_2 (mod\ m_2) \\ x \equiv a_3 (mod\ m_3) \\ \dots \\ x \equiv a_i (mod\ m_i) \]

但是我们仍然可以用古老的扩展欧几里得算法来解这个问题，合并方程即可。

假设我们正在解第\(k\)个方程，设\(m=\prod_{i=1}^{k-1}\)，\(x\)为满足\(1\)~\(k-1\)个方程的解。我们知道，\(tm+x\)为前\(k-1\)个方程的通解，那么我们只需要在这一轮求出\(k\)并更新答案即可，也就是解：

\[ tm_{k-1} + x_{k-1} \equiv a_k(mod\ m_k) \\ tm_{k-1} + m_k y \equiv a_k – x_{k-1}(mod\ m_k) \]

放进 \(exgcd\) 里面解下即可。

代码

// POJ2891.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 200;
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), z = x;
    x = y, y = z - (a / b) * y;
    return d;
}
int main()
{
    ll n;
    while (~scanf("%lld", &n))
    {
        ll x, y, a, b, k;
        scanf("%lld%lld", &a, &b);
        ll lcm = a, ans = b;
        bool flag = true;
        n--;
        while (n--)
        {
            scanf("%lld%lld", &a, &b);
            b = (b - ans % a + a) % a;
            ll d = exgcd(lcm, a, x, y);
            if (b % d)
                flag = false;
            else
                k = x * (b / d);
            ans += k * lcm;
            lcm = lcm / d * a;
            ans = (ans % lcm + lcm) % lcm;
        }
        if (flag)
            printf("%lld\n", ans);
        else
            puts("-1");
    }
    return 0;
}