这是本蒟蒻的第一篇题解，也是本蒟蒻的第一篇黄题题解。

题目传送门

题目大意

给定 $n$ 个数，每个数可利用无数次，输出这些数不能组合出来的数的个数，如果有无限个，输出 -1。

思路

本题考查动态规划+数论，因为标签里有。

1.如何判断有无限种数量的汤圆不能买到？

设 $n$ 个数的最大公约数为 $x$，判断如果 $x$ 不等于 $1$，直接输出 -1。

为什么?

首先，既然这 $n$ 个数并不互质，也就是当 $x$ 不等于 $1$ 时，表明这时只能凑出 $x$ 的倍数的数，因此就有无数个数无法凑出。举个例子，$6,8$ 的最大公约数为 $2$，这时类似 $1,3,5,9,13$ 等数都凑不出来，就有无数个数凑不出来，输出 -1。

2.动态转移方程与 dp 上限

1.动态转移方程

$dp_i$ 为是否可以通过这给定的 $n$ 个数组合出 $i$，$1$ 代表可以组合，$0$ 代表不能组合。最后统计有多少个 $dp_i$ 为 $0$，直接输出答案。
初始化 $dp_0$ 等于 $1$，也就是不买任何汤圆，容易推出当 $dp_i-a_j$ 等于 $1$ 时，将 $dp_i$ 赋值为 $1$。

2.dp 上限

这里萌新自愧不如，由于不会推导上限，大家可以移步至这篇题解，学习一下。或者枚举到 $10^6$ 保险，反正不会超时。

AC code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20+5;//规格数量 
const int MAXM=1e5+10;//dp数组大小 
bool dp[MAXM];
int a[MAXN];
int n;

int gcd(int x,int y){//计算最大公约数 
	while(y!=0){
		int temp=y;
		y=x%y;
		x=temp;
	}
	return x;
}

int main(){
	scanf("%d",&n);
	int flag=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		flag=gcd(flag,a[i]);//提取公因数 
	}
	if(flag!=1){//判断是否互质 
		printf("-1");
		return 0;
	}
	dp[0]=1;//dp初始化
	for(int i=1;i<=MAXM;++i){//枚举到上限 
		for(int j=1;j<=n;++j){
			if(i>=a[j]){
				if(dp[i-a[j]]){
					dp[i]=1;
					break;//一旦能组合就跳过 
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=MAXM;++i)
		ans+=!dp[i];//统计答案 
	printf("%d",ans);
	return 0;
}

如果对你有帮助，能不能用你的小手点个关注或者是下面的大拇指，我会很 happy 的，awa。冲击66粉！！！

The End