题面：
水果糖被包成 \(n\) 颗一包和 \(m\) 颗一包的两种，用这两种包装来组合，不能拆包卖。
在 \(4\) 颗一包和 \(7\) 颗一包的情况下，最大不能买到的数量是 \(17\) 。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
数论：组合数学
存在两个正整数 \(p\) 和 \(q\)，有这样一个组合 \(xp+yq\)（\(x\) 倍的 \(p\) 和 \(y\) 倍的 \(q\)），
试问其无法组成的数中最大的一个是？
标准解法：裴蜀定理
公式：\((p-1)(q-1)-1\)
然而，关于数论题，当我们对该题涉及的公式没有概念时，如何突破困境？
分析思路
是否有解：考虑最大公约数（gcd）
当 \(p\) 和 \(q\) 存在最大公约数 \(d\) 时，能组合出的数一定是 \(d\) 的倍数。
打表找规律
#include<bits/stdc++.h>
using namespace std;
//暴力法一：(6/11)
bool dfs(int i, int n, int m) {
//如果余数为0，则可以组合
if (!i) return true;
if (i >= n && dfs(i - n, n, m)) return true;
if (i >= m && dfs(i - m, n, m)) return true;
return false;
}
int main()
{
int n, m;
cin >> n >> m;
int res = 0;
//设一个较大数（此处为1000），若超过就认为其有解
for (int i = 1; i <= n * m; i++)
if (!dfs(i, n, m)) res = i;
cout << res << endl;
}
//暴力法二：(9/11)
int main()
{
int n, m;
bool flag;
cin >> n >> m;
int res = min(n, m) - 1;
for (int i = min(n, m); i < n * m; i++) {
flag = false;
for (int j = 0; j * n <= i; j++) {
if ((i - j * n) % m == 0) {
flag = true;
break;
}
}
if (!flag) res = i;
}
cout << res;
}
简单DP优化[1]
如果 \(i\) 可以被组合出来，那么 \(i-n\) 或 \(i-m\) 一定可以被组合出来。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, res = 1;
bool dp[N];
int main()
{
cin >> n >> m;
dp[0] = true;
if (n > m) swap(n, m);
for (int i = n; i < n * m; i++) {
if (dp[i - n])
dp[i] = true;
else if (i >= m && dp[i - m])
dp[i] = true;
else res = i;
}
cout << res;
}