A41795. 组合
填空题
困难
知识点
题目描述
组合
题目描述：
某商家将一种汤圆按照数量不同，分装成N种规格来售卖。这样的售卖方式会限制一些数量的汤圆不能买到。
例如：
N=2，2种规格的汤圆分别装3个和5个，这种情况下限制了1，2，4，7四种数量的汤圆不能买到。
给出N及N种规格的汤圆数量，请计算出有多少种数量的汤圆不能买到，如果有无限种数量的汤圆不能买到就输出“-1”。
输入描述：
第一行输入一个正整数N（1<N<20），表示有N种规格的汤圆
第二行输入N个各不相同的正整数（1<正整数<100），表示每种规格的汤圆数量，且正整数之间以一个空格隔开
输出描述：
输出在这种情况下有多少种汤圆数量是不能买到的，如果有无限种数量的汤圆不能买到就输出“-1”
样例输入：
2
3 5
样例输出：
4
参考答案
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[25],f[10005],g;
int gcd(int a,int b){
if (a%b==0) return b;
else return gcd(b,a%b);
}
int main()
{
cin>>n>>a[0];
g=a[0];
f[a[0]]=1;
for(int i=1;i<n;i++){
cin>>a[i];
g=gcd(g,a[i]);
f[a[i]]=1;//标记a[i]能被取到
}
//n个数字如果不能互质
//则不能组合的数字有无限个
if(g!=1){
cout<<-1<<endl;
return 0;
}
//将所有可能的组合标记
for(int i=1;i<10000;i++){
if(f[i]==1){
for(int j=0;j<n;j++)
f[i+a[j]]=1;
}
}
int ans=0;
for(int i=1;i<10000;i++)
if(f[i]==0) ans++;
cout<<ans<<endl;
return 0;
}
上一题
下一题