每日算法打卡：买不到的数目

算法
964 words

原题链接

1205. 买不到的数目

题目难度：简单

题目来源：第四届蓝桥杯省赛C++ A组,第四届蓝桥杯省赛Java C组

题目描述

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式

两个正整数 n,m，表示每种包装中糖的颗数。

输出格式

一个正整数，表示最大不能买到的糖数。

数据范围

2≤n,m≤1000，
保证数据一定有解。

输入样例：

1
4 7

输出样例：

1
17

题目分析

这道题其实就是非常经典的一道数学题目，题目意思也很简单，就是给两个数，问最大的不能凑出来的数是多少

假设我们不知道这个数学定理，如何尽力去分析呢，首先假设这两个数字是p和q，他们的最大公因数是d，那么对于大于p和q，且因数中没有d的数字是一定凑不出来的，反过来，那么只要他们的最大公因数d是大于1的，就一定是无解的，那么这种情况就可以排除

例如6和2，他们的最大公因数是2，那么对于大于6的奇数，因数没有2，因此也无法用6和2凑出来

那么如果p和q互质，也就是他们的最大公因数为1，是否一定有解呢，答案是肯定的，因为这里有一个定理叫做裴蜀定理，他的内容是如果p和q的最大公因数为d，那么一定存在两个整数满足$ap+bq=d$，那么如果这两个数互质，就有$ap+bq=1$，当我们要凑的数m足够大时，就有$amp+bmq=m$，这里我们做一共恒等变形$(am-q)p+(bm+p)q=m$因为题目要求是正整数，那么只要m足够大，p和q的系数就一定是正整数，就是可以用p和q凑出m了

再往后思考似乎也分析不出什么了，这里我们就要用到一个做题的方法，打表找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

bool dfs(int m, int p, int q)
{
    if (m == 0) return true;
    if (m >= p && dfs(m - p, p, q)) return true;
    if (m >= p && dfs(m - q, p, q)) return true;
    return false;
}

int main()
{
    int p, q;
    int res = 0;
    cin >> p >> q;
    for (int i; i <= 1000; i++)
    {
        if (!dfs(i, p, q)) // 找到最大的一个不能被凑出来的数
            res = i;
    }
    cout << res << '\n';
    return 0;
}

然后我们尝试不同的输入，可以得到

1
2
3
4
5
6
7
8
9
/*
3 2 1
3 4 5
3 5 7
3 7 11
3 8 13

3 n m=2n-3
*/

这里我们发现还是有一些规律的，第二项多1，第三项就多2

然后我们再把第一项再进行枚举

通过总结规律，其实是能猜出来m = (p-1)(q-1)-1

这个结论其实是一个定理，他的证明极其复杂，这里给出链接525. 小凯的疑惑

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

示例代码

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
int main()
{
    int p, q;
    cin >> p >> q;
    cout << p * q - p - q << '\n';
    return 0;
}
Comments