AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 525. 小凯的疑惑    原题链接    简单

作者: 作者的头像   yxc ,  2019-07-28 23:23:18 ,  所有人可见 ,  阅读 7970


81


69

算法

(数论) $O(1)$

结论:

如果 $a, b$ 均是正整数且互质,那么由 $ax + by, x \ge 0, y \ge 0$ 不能凑出的最大数是 $ab - a - b$。

下面给出证明:

首先证明 $ab - a - b$ 不能被 $ax + bx, x \ge 0, y \ge 0$表示出。
反正法,假设 $ab - a - b = ax + by$,那么 $ab = a(x + 1) + b(y + 1)$,由于 $a | ab, a | a(x + 1)$,所以 $a | b(y + 1)$,由于 $a, b$ 互质,所以 $a | (y + 1)$,由于 $y \ge 0$,所以 $a <= y + 1$,所以 $b(y + 1) \ge ab$。同理可得 $a(x + 1) \ge ab$,所以 $a(x + 1) + b(y + 1) \ge 2ab \gt ab$,矛盾。

证明 $ab - a - b + d, d > 0$ 一定可以表示成 $ax + by, x, y \ge 0$ 的形式,可以参考这篇博客。

时间复杂度分析

计算 $ab - a - b$ 的时间复杂度是 $O(1)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    LL a, b;
    cin >> a >> b;
    cout << a * b - a - b << endl;

    return 0;
}

11 评论


用户头像
acwing_233   2021-04-16 16:42      1    踩      回复

666


用户头像
brivia   5个月前         踩      回复

若 $gcd(a, b) = d > 1$ 怎么做?

用户头像
发廊探险家   5个月前      2    踩      回复

这种情况没解,不会出现的

用户头像
nope_ck   5个月前      1    踩      回复

互质才有这个结论


用户头像
努力挣钱   2021-10-20 18:44         踩      回复

参考的博客,最后的推出有问题。应该是 $(p-1+B)q + (A-1)p + k * min(p,q) $

用户头像
努力挣钱   2021-10-20 18:46         踩      回复

然后 因为 $ k>=0,(p-1+B)>=0,(A-1)>=0 $,所以得证


用户头像
石犇   2021-04-29 12:03         踩      回复

诡辩

用户头像
Aigrl   10个月前      1    踩      回复

好不礼貌啊qwq

用户头像
xhQYm   8个月前      1    踩      回复

都是严格证明了,怎么是诡辩?你写一个正解?


用户头像
bug_generator   2021-04-29 11:35         踩      回复

反证法上面一行,$ax+by$


用户头像
bug_generator   2021-04-29 11:33         踩      回复

反证法,写错字了


你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息