蓝桥杯2017年第八届真题-包子凑数 （C++代码）

参考代码:

#include<bits/stdc++.h>
constexpr auto Inf = 0x3F3F3F3F;
#define Loc freopen("baka.in", "r", stdin)
typedef long long LL;
using namespace std;

const int SIZE = 1E4 + 7;
vector<int> vec;
bool Vis[SIZE];

int Gcd(int A, int B) {
	return !B ? A : Gcd(B, A % B);
}

int main() {
	ios::sync_with_stdio(false);
	int Tot; cin >> Tot;
	for (int pos = 1, Tmp; pos <= Tot; pos++)
		cin >> Tmp, vec.push_back(Tmp);
	int Judg = *vec.begin();
	for (int pos = 1; pos < vec.size(); pos++)
		Judg = Gcd(Judg, vec[pos]);
	if (Judg != 1) {
		puts("INF"); return 0;
	} Vis[0] = true;
	for (int pos = 0; pos < vec.size(); pos++)
		for (int Ind = 0; Ind + vec[pos] < SIZE; Ind++) {
			if (Vis[Ind])
				Vis[Ind + vec[pos]] = true;
		}
	int ans = 0;
	for (int pos = 0; pos < SIZE; pos++)
		ans += !Vis[pos];
	cout << ans << endl;
}