蓝桥杯 包子凑数（完全背包、裴蜀定理、赛瓦维斯特定理）
一、题目来源
OJ传送门
参考题解
\(2017\)年蓝桥杯软件类省赛\(C++\)语言大学\(A\)组第\(8\)题"包子凑数"，一道数论题。
2022年4月青少年蓝桥杯赛第二次省赛初级+中高级组第三题
这也太\(tm\)内卷了，拿这个来考三年级的小孩子！真是太\(BT\)了！还第三题！！！
二、解题思路
- 裴蜀定理
简单来说，我们设 \(d = gcd(a,b)\)，那么对于方程\(ax+by=d\)，一定存在一组整数解。并且对于方程 \(ax + by = z\)，如果满足 \(d∣z\)，那么方程一定有整数解，否则无整数解。
根据裴蜀定理，当所有种类的蒸笼包子数的最大公约数不为\(1\)时，凑不出的包子数为无限多，因为无论蒸笼怎么组合都必须得是\(gcd\)得倍数，\(gcd\)不为\(1\)一定会有凑不出的。
三、实现代码
#include
using namespace std;
/**
测试用例
2
3 5
答案
4
*/
typedef long long LL;
const int N = 1e6 + 5;
LL f[N]; //表示凑出j个包子的方法总数
int a[N]; //每种规格中包子的数量
int ans; //组装不出来的包子个数
//最大公约数，辗转相除法
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
//赛瓦维斯特定理 : 两个互质数a,b表示不出来的最大数字是 a?b?a?b
//下面排序后找出极小值与次小值，它们的乘积再减去极小和次小，就是极限值
sort(a + 1, a + 1 + n);
int m1 = a[1], m2 = a[2]; //最小和次小
int M = m1 * m2 - m1 - m2;
//求出所有数字的最大公约数
int g = a[1];
for (int i = 2; i <= n; i++) g = gcd(g, a[i]);
/*裴蜀定理:如果所有数字的最大公约数大于1，那么必然存在无法表示出的数字。
不互质栗子:
比如3 和 6 两种规格，能组装的就是 3,6,9,12,15,这个变化就是它们的最大公约数3。
比如3 和 6 和 9 三种规格, 能组装的也是 3,6,9,12,15,这个变化就是它们的最大公约数3。
此时 ，类似于 1,2,4,5,7,...之类的数字均是无法凑出的，有无穷多个。
互质栗子:
比如 3 和 4 两种规格， 能组装的就是 3,4,6,7,8,9,10,11,12...., 根据赛瓦维斯特定理，我们知道，最大的不能组装的数字是3*4-3-4=5
比如 3 和 4 和 6 三种规格，因为3，4就能组装出5以上的所有数字，所以我们只需要从最小a[1]到 M 中查找即可。
*/
if (g > 1) {
cout << "INF" << endl; // cout << -1 << endl; //青少组要求输出-1
return 0;
}
/**
完全背包
f[j]表示凑出j个包子的方法总数，简单说就是如果f[j]>0就凑得出，f[j]=0就凑不出。
递推式 f[j]=f[j?第i种蒸笼包子数]+1 (f[j?第i种蒸笼包子数]>=1)
当j?第i种蒸笼包子数是可以凑成的，那么只需对其+第i种蒸笼包子数就可以凑成j个包子数。
*/
f[0] = 1; // 0个包子这个状态是合法的，是可以到达的状态。而且只能是一种方案，就是不管是哪种规格，一概不要
for (int i = 1; i <= n; i++)
for (int j = 1; j <= M; j++)
if (j >= a[i] && f[j - a[i]]) f[j]++;
//枚举每个可能的数字，如果这个数字存在1种以上的方案，就是可以凑出，否则就是无法凑出
for (int i = 1; i <= M; i++)
if (!f[i]) ans++;
//输出答案
cout << ans << endl;
return 0;
}
-
赛瓦维斯特定理
如果能够凑出的数有限，那么到达某个界限后都是凑得出的，这个界限为\(a*b-a-b\)。这里由于有多个数字，我们可以采用最大做为\(a\),次大做为\(b\)来求解。 -
递推关系
\(dp[i]\)表示凑出\(i\)个包子的方法总数，简单说就是如果其\(>=1\)就凑得出，\(==0\)就凑不出。
状态转移方程： \(dp[i]=dp[i-\)第\(j\)种蒸笼包子数\(]+1\) (\(dp[i-\)第\(j\)种蒸笼包子数\(]>=1\))
当\(i-\)第\(j\)种蒸笼包子数是可以凑成的，那么只需对其+第\(j\)种蒸笼包子数就可以凑成\(i\)个包子数。