历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 204. 表达整数的奇怪方式原题链接困难

作者：

墨染空 , 2019-08-20 13:38:48 , 所有人可见 , 阅读 20206

525

226

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

1. 将式子等价转换

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

$x \equiv m_1 (\%\ a_1)$

$x \equiv m_2 (\%\ a_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$都是正数）。

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

我们已知$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$

3. 找到最小正整数解

我们知道一个性质：

②$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})$，使其为正整数且最小。

4. 等效替代：

由②式带入

新的$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$，那么问题又回到了第一步。

5. 总结

我们的做法相当于每次考虑合并两个式子，将这$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;
}

198 评论

吾皇_7 2022-08-22 21:56

初中生大佬牛逼！感觉我这几年白活了一样捏qwq

ཌༀཉ慕辰ༀད 2023-01-18 17:49

我上大学之前就没接触过电脑，估计我也白活了

彭羽攀pyp 2023-05-22 13:00 回复了 ཌༀཉ慕辰ༀད 的评论

我也是呜呜呜

墨染空 2023-06-19 01:44

我也是呜呜呜

itn 3个月前

我上大学后才开始接触算法

AlexVagrant 2023-07-03 19:06

补充一下使用线性丢番图方程求$k1$所有的解

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

$k_1\cdot a_1 + k_2\cdot (-a_2) = gcd(a_1, -a_2)$

对a1, a2使用扩展欧几里德函数得到d

$k_1\cdot a_1 + k_2\cdot a_2 = d$

如果$d|m_2-m_1$则有解。两边乘$\frac{m_2-m_1}{d}$ 右边就变为了$m_2-m_1$

$k_1\cdot a_1\cdot \frac{m_2-m_1}{d} + k_2\cdot a_2\cdot \frac{m_2-m_1}{d} = m_2-m_1$

有解的情况下得到一组特解

$k_1 = k_1\cdot \frac{m_2-m_1}{d}$

$k_2 = k_2\cdot \frac{m_2-m_1}{d}$

注意这里$k_1$表示特解

代码中表现为 k1 *= (m2-m1) / d

### 找到所有的解

将一组特解带回方程

$k_1\cdot a_1 + k_2\cdot a_2 = c$

$k_1 += a_2/d$的同时$k_2 -= a_1/d$，方程右边不变

$(k_1+ \frac{a_2}{d})\cdot a_1 + ({k_2-\frac{a_1}{d}})\cdot a_2 = a_1\cdot k_1 + a_2\cdot k_2 + a_1\cdot \frac{a_2}{d} - a_2\cdot \frac{a_1}{d} = c$

于是得到所有情况的解集

$k1 = k_1 + (\frac{a_2}{d})\cdot k$

$k2 = k_2 + (\frac{a_1}{d})\cdot k$

#### 找到最小正整数解

模尽倍数后，剩下的余数就是最小的正整数解

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

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

代码中表现为

LL t = a2/d;
k1 = (k1 % t + t) % t;

新的$x$为:
$$ x= (k_1 + \frac{a_2}{d} \cdot k) \cdot a_1 + m_1 \\ = k_1\cdot a_1 + m_1 + \frac{a_2\cdot a_1}{d} \cdot k $$

$k_1\cdot a_1 + m_1$ 为合并后的$a_1$，$\frac{a_2\cdot a_1}{d} \cdot k$为新的$m_1$

LL m = abs(a1 / d * a2);
a1 = k1 * a1 + m1;
m1 = m;

18726792945 2023-07-22 22:09

你最后的m1和a1写反了

AlexVagrant 2023-07-23 23:03 回复了 18726792945 的评论

是的感谢纠正！

LL m = abs(a1 / d * a2);
m1 = k1 * a1 + m1;
a1 = m;

cai_xing 2023-08-13 22:10 回复了 AlexVagrant 的评论

写得真好，可以放到你的题解里面

goodboy_8 2023-09-17 21:06

妙！！大佬写个题解吧

今日臭明日香 6个月前

所有过程都明白但是为什么最后输出的是m1的值而不是x的值呢？

AlexVagrant 6个月前回复了今日臭明日香的评论

我们只需要继续找：$x=k∗a0+m0=k3∗(−a3)+m3$ 那么问题又回到了第一步。

这里引用楼主的回答，可以看出 $m1$ 和 $x$ 是等价的。实际代码中只在求解$m1$，所以这里输出的是 $m1$

爱情丶眨眼而去 2022-11-08 23:28

# 初等数论之求解二元不定方程

定理1:

设二元一次不定方程
$$ ax + by = c \\hspace{1cm} (1) $$

(其中a, b, c是整数, 且a, b都不是0), 假定有一组整数解，$x=x_0, y=y_0$。

则原式的一切整数的通解可以表示成
$$ \\left\\{ \\begin{aligned} x = x_0 - \\frac b {(a, b)}t, & \\\\ & (t \\in z) \\\\ y = y_0 + \\frac a {(a, b)}t, & \\\\ \\end{aligned} \\right. $$
定理2:

$\\hspace{1cm}(1)$式有整数解等价于$(a, b)|c$。