我作为一个初中蒟蒻，听y大视频听了5遍还不懂，快哭了。然后终于（好像）搞懂，写成题解加深一下记忆...

将式子等价转换

对于每两个式子（我们考虑将其合并）：

$x \equiv a_1 \%\ m_1$

$x \equiv a_2 \%\ m_2$

则有：

$x = k_1 * a_1 + m_1$

$x = k_2 * a_2 + m_2$

进一步：

$k_1 * a_1 + m_1 = k_2 * a_2 + m_2$

移项：

$k_1 * a_1 - k_2 * a_2 = m_2 - m_1$

也就是：

① $k_1 * a_1 + k_2 * (-a_2) = m_2 - m_1$

也就是我们需要找到一个最小的$k_1, k_2$，使得等式成立（因为要求$x$最小，而$a$和$m$都是正数）。

用扩展欧几里得算法找出一组解

我们已知$a_1,m_1,a_2,m_2$，可以用扩展欧几里得算法算出一个$k'_1, k'_2$使得：

$k'_1 * a_1 + k'_2 * (-a_2) = gcd(a_1, -a_2)$

无解判断：

若$gcd(a_1, -a_2) \nmid m_2 - m_1$，则无解。

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

承接上文，我们只需让$k_1, k_2$分别扩大$y$倍，则可以找到一个$k_1, k_2$满足①式：

$k_1 = k'_1 * y, k_2 = k'_2 * y$

找到最小正整数解

我们知道一个性质：

②$k_1 = k_1 + k *\frac{a_2}{d}$

$k_2 = k_2 + k *\frac{a_1}{d}$

$k$为任意整数，这时新的$k_1, k_2$仍满足①式。

证明：

将新的$k_1, k_2$带入式子得:

$(k_1+k*\frac{a_2}{d})*a_1+(k_2+k*\frac{a_1}{d})*(-a_2)=m_2-m_1$

拆出来：

$k_1*a_1+k*\frac{a_2*a_1}{d}+k_2*(-a_2)+k*\frac{a_1*(-a_2)}{d}=m_2-m_1$

交换一下顺序，把负号拆出来：

$k_1*a_1+k_2*(-a_2)+k*\frac{a_2 * a_1}{d}-k*\frac{a_1 * a_2}{d}=m_2-m_1$

那个同加同减可以消掉：

$k_1*a_1+k_2*(-a_2)=m_2-m_1$

这个式子和①是一样的，因①成立，故此式也成立。

要找一个最小的非负整数解，我们只需要让

$k_1 = k_1 \%\ abs(\frac{a_2}{d})$

$k_2 = k_2 \%\ abs(\frac{a_1}{d})$

即可找到当前最小的$k_1, k_2$的解，即此时的$k$为$0$。

$Q$：此处为什么要取绝对值呢

$A$：因为不知道$\frac{a_2}{d}$的正负性，我们在原基础上要尽量减多个$abs(\frac{a_2}{d})$，使其为正整数且最小。

等效替代：

由②式带入

新的$x$为：

$x = (k_1 + k * \frac{a_2}{d}) * a_1 + m_1$

$= k_1 * a_1 + m_1 + k * \frac{a_2 * a_1}{d}$

$= k_1 * a_1 + m_1 + k * lcm(a_1, a_2)$ ③

$Q$:这里，$k$都为$0$了，为什么还要算呢？

$A$:因为这只是前两个式子得最小$k$，有可能遇到下一个式子后面被迫要扩大

在③中，我们设$a_0 = lcm(a_1, a_2), m_0 = k_1 * a_1 + m_1$

那么：

③ $ = k * a_0 + m_0$

这个形式与一开始我们分解的形式是不是特别像呢？

没错！假设之后又来了一个$a_3, m_3$

我们只需要继续找：

$x = k * a_0 + m_0 = k_3 * (-a_3) + m_3$，那么问题又回到了第一步。

总结

我们的做法相当于每次考虑合并两个式子，将这$n$个式子合并$n - 1$次后变为一个式子。最后剩下的式子就满足我们的答案。

注意：

$lcm(a_1, a_2)$和$\% \frac{a_2}{d}$，需要取绝对值。又因为$d = gcd(a_1, -a_2)$，我们不知道$a_1$的正负性（可能是上一步推过来的）。
$\% \frac{a_2}{d}$，需要取绝对值，膜负数的话，不会取到正解；

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long LL;

int 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, y, x);

    y -= a / b * x;

    return d;

}

LL inline mod(LL a, LL b){

    return ((a % b) + b) % b;

}

int main(){

    scanf("%d", &n);

    LL a1, m1;

    scanf("%lld%lld", &a1, &m1);

    for(int i = 1; i < n; i++){

        LL a2, m2, k1, k2;

        scanf("%lld%lld", &a2, &m2);

        LL d = exgcd(a1, -a2, k1, k2);

        if((m2 - m1) % d){ puts("-1"); return 0; }

        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));

        m1 = k1 * a1 + m1;

        a1 = abs(a1 / d * a2);

    }

    printf("%lld\n", m1);

    return 0;

}

巴特西

AcWing 204. 表达整数的奇怪方式 / Strange Way To Express Integers

将式子等价转换

用扩展欧几里得算法找出一组解

无解判断：

找到最小正整数解

证明：

等效替代：

总结

最新文章

热门文章