AcWing 1205. 买不到的数目

题面：
水果糖被包成 \(n\) 颗一包和 \(m\) 颗一包的两种，用这两种包装来组合，不能拆包卖。
在 \(4\) 颗一包和 \(7\) 颗一包的情况下，最大不能买到的数量是 \(17\) 。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

原题链接：1205. 买不到的数目 - AcWing

数论：组合数学

存在两个正整数 \(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;
}