高师本科化学实验教学体系建设与创新型人才培养 教学成果奖申报网站,seo门户网,wordpress fla插件,上海市网站建设题目#xff1a;
时间限制: 1Sec 内存限制: 128MB 提交: 1049 解决: 365
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼#xff0c;其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼#xff0c;可以认为是无限笼。
每当有顾客想买X…题目
时间限制: 1Sec 内存限制: 128MB 提交: 1049 解决: 365
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼可以认为是无限笼。
每当有顾客想买X个包子卖包子的大叔就会迅速选出若干笼包子来使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼分别能放3、4和5个包子。当顾客想买11个包子时大叔就会选2笼3个的再加1笼5个的也可能选出1笼3个的再加2笼4个的。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼分别能放4、5和6个包子。而顾客想买7个包子时大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
第一行包含一个整数N。(1 N 100) 以下N行每行包含一个整数Ai。(1 Ai 100)
输出
一个整数代表答案。如果凑不出的数目有无限多个输出INF。
样例输入
2 4 5
样例输出
6
分析
拿到这道题我就知道要用完全背包来判断是否装满问题但却不清楚怎样判无限的情况猜想和素数有关因为哥德巴赫猜想任意大于2的偶数都可写成两个质数之和。但是我没想出来后来问了会长才知道要用拓展欧几里得判是否所有数互质好的吧。特殊情况不构成的数为INF时充分条件是包子的数目最大公约数都不为1即包子的数目都为一个数的倍数这个数不是1{欧几里得扩展变形}但数据挺弱的不考虑特判也能过。
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int inf0x3f3f3f3f;
const int M1e610;
int t,ans;
int a[110],dp[M];
int gcd(int x,int y){return y0?x:gcd(y,x%y);
}
int main(){scanf(%d,t);scanf(%d,a[1]);ansa[1];for(int i2;it;i){scanf(%d,a[i]);ansgcd(ans,a[i]);}if(ans!1) printf(INF\n);else{memset(dp,0,sizeof(dp));dp[0]1;for(int i1;it;i){for(int j0;jM;j){if(dp[j])dp[ja[i]]1;}}int num0;for(int i1;iM;i)if(!dp[i])num;printf(%d\n,num);}return 0;
}
