题目描述

关系

内容

小明开了一家糖果店。

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

糖果不能拆包卖。

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

$2\le n,m\le 1000$，
保证数据一定有解。

输入样例：

4 7

输出样例：

17

问题分析

最初思路

思路分析

这道题是一个经典的问题。裴蜀定理：

如果 p、q 不互质，并且 ${\displaystyle gcd(p,q)=d>1}$ ，那么就一定凑不出来最大数。因为只要不是 d 的倍数就一定凑出来。例如我们有 p、q 为 6，2。

如果我们事先不知道这个结论如何做这道题呢？

如果我们能够得出：

如果 p、q 不互质，并且 ${\displaystyle gcd(p,q)=d>1}$ ，那么就一定凑不出来最大数。因为只要不是 d 的倍数就一定凑出来。例如我们有 p、q 为 6，2。

那么就有眉目了。

但是我们可以通过打表找出规律。而打表考验的其实是暴力。那么这道题如何写暴力解法呢？

第一，暴力解法难处在于如何规定其上界呢？不用确定其上界，我们可以自己选择一个足够大的数，例如 1000，然后再进行枚举。

第二，枚举的策略是什么？我们可以先从 ${\displaystyle x=3}$ 开始枚举 y：

执行流程设计

总结

1. 对于这种题目，要么是定理题，要么是找规律。如果决定找规律，那么最好的办法就是打表找规律。

代码实现

打表

#include <bits/stdc++.h>
using namespace std;

int n, m;

// n m 能否凑出 a?
bool dfs(int a, int n, int m) {
    if (!a) return true;
    
    if (a >= n && dfs(a - n, n, m)) return true;
    if (a >= m && dfs(a - m, n, m)) return true;
    
    return false;
}

int main()
{
    cin >> n >> m;


    int res = 0;
    for (int i = 1; i <= 1000; i++) {
        if (!dfs(i, n, m)) res = i;
    }
    
    cout << res;
    return 0;
}

结论

#include <bits/stdc++.h>
using namespace std;

int n, m;

int main()
{
    cin >> n >> m;
    
    cout << (n - 1) * (m - 1) - 1;
    return 0;
}