题解 | #曹冲养猪#

曹冲养猪（模板题）

题目大意

求一个最小的非负整数 $x$ , 满足（为了方便，将最终解的x换成大写 $X$ ） $\begin{cases} X \equiv a_1 (\bmod m_1) \\ X \equiv a_2 (\bmod m_2) \\ \cdots \\ X \equiv a_n (\bmod m_n) \end{cases}$

思路

由定义得

$X = k_1 \times m_1 + a_1 \\ X = k_2 \times m_2 + a_2$

移项整理

$k_1 \times m_1 + k_2 \times (-m_2) = a_2 - a_1 \tag{1}$

类似于扩展欧几里得算法式 $ax + by = gcd(a, b)$ ，因此用此算法求出两个整数 $(x, y)$ 符合 $xm_1 + y(-m_2) = gcd(m_1,-m_2)$ ，

若 $(a_2 - a_1) \% gcd(m1, -m_2) \not = 0$ ，则方程无解。

设

$d = gcd(m_1 - m_2), y = \frac{a_2 - a_1}{d}$

我们知道性质：(证明跳过)

$x = x + k \times \frac{m_2}{d} \tag 2 \\ y = y + k \times \frac{m_1}{d}$

那么，为了找到一个最小非负整数，易知只需让（2）式中的 $k$ 为0，可得答案为 $x = x \% abs(\frac{m_2}{d}) \\ y = y \% abs(\frac{m_1}{d})$

带入可得

$\begin{aligned} X &= (x + k \times \frac{m_2}{d}) \times m_1 + a_1 \\ &= x \times m_1 + k \times \frac{m_1m_2}{d} + a_1\\ &= x \times m_1 + k \times lcm(m_1, m_2) + a_1 \end{aligned} \tag 3$

这里，我们设 $m_0 = lcm(m_1, m_2), a_0 = x \times m_1 + a_1$ ，可得

$X = (3) = k \times m_0 + a_0$

总结

依次合并 $n - 1$ 个方程，最后即为最终答案。

code

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
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, y, x);
    y -= a / b * x;
    return d;
}
LL mod (LL a, LL b) { 
    return ((a % b) + b) % b;
}
int main() {
    int n;
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld %lld", &m1, &a1);
    for (int i = 1; i < n; i++) {
        LL a2, m2, x, y;
        scanf("%lld %lld", &m2, &a2);
        LL d = exgcd(m1, -m2, x, y);
        if ((a2 - a1) % d) return puts("-1"), 0;
        x = mod(x * (a2 - a1) / d, abs(m2 / d));
        a1 = x * m1 + a1;
        m1 = abs(m1 / d * m2);
    }
    printf("%lld\n", a1);
    return 0;
}

第一次发题解，如有错误希望可以矫正