一、题目描述

P8646 [蓝桥杯 2017 省 AB] 包子凑数

二、题目简析

首先，要理解一个定理——裴蜀定理：
若任意整数 \(a\) 和 \(b\)，且有 \(m = \text{gcd}(a, b)\)，对任意整数 \(x\) 和 \(y\)，\(ax+by=c\)，则 \(m~|~c\)。
由该定理，我们知道 \(ax+by\) 一定是 \(\text{gcd}(a, b)\) 的倍数。

利用裴蜀定理，再来看本题，可以得到两个结论：

• 1、若 \(\text{gcd}(a, b) == 1\)，则无法表达的数目是有限个。
• 2、若 \(\text{gcd}(a, b) > 1\)，则无法表达的数目是无限个。

先判断所有元素的 gcd 是否等于1，若大于，则输出 INF；若等于，则在一定范围内（如 1e5）求出所有可以表示的元素，再统计不能表示的元素个数。我们可以采用动态规划来统计：
令 \(dp[k]=\) 能否表示该数 （true or false）

dp[0] = true;
for (int i = 0; i < n; i++)
{
	for (int j = A[i]; j <= N; j++)
		dp[j] = dp[j] | dp[j - A[i]];
}

三、AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
const int MAX = N + 3;

int A[MAX], n;
bool dp[MAX];

int gcd(int a, int b)
{
	if (b == 0)    return a;
	return gcd(b, a % b);
}

bool check(void)
{
	int res = A[0];
	for (int i = 1; i < n; i++)
		res = gcd(res, A[i]);
	return res == 1;
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];
		
	if (check())
	{
		dp[0] = true;
		for (int i = 0; i < n; i++)
		{
			for (int j = A[i]; j <= N; j++)
				dp[j] = dp[j] | dp[j - A[i]];
		}
		int ans = 0;
		for (int i = 1; i <= N; i++)
			if (!dp[i])
				ans++;
		cout << ans << endl;
	}
	else
		cout << "INF" << endl;	
	
	return 0;	
}

完