包子凑数（未解决）
题目 包子凑数
思路分析
乍一看感觉和前面的那个砝码称重差不多 也是用count或bool作属性看选出的数量
但是这里问的是选不出的数量 一开始理所当然的直接把总的减去选的出的就是选不出的
但发现并不是这么简单
题目说会出现有无限个数被凑不出来的， 说明这些数的gcd不是1
这里用到裴蜀定理 ，任意两个数的组合必定是他们gcd的的倍数，同样可以推广到更多数：
如果这些数的gcd是d，那么他们的组合是d的倍数，如果d不是1，那么必然有无限个数无法被组合出来。
所以，要先写个欧几里得算法，两两求下gcd，看gcd是否大于1。
欧几里得算法：gcd(a,b)=gcd(b,a%b)。当余数为0时，当前算式的除数就是a和b的gcd。 那么，gcd为1呢？最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的数是：(a−1)(b−1)−1 当数字更多的时候，这个上界必然更小（可选的数字变多了），而99和98是100内最大的互质的数，所以这个上界选择10000
那么下面的事情就是看这么多数中有多少个不能被组合出来，回到了刚开始分析的完全背包问题
大概就是 要先计算一下公因数 公因数不是1的话就一定有INF个求不出来
把这个情况解决了 然后就是前面那种用count或bool的完全背包求方案数问题
emmm 放弃这题了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m;
int w[110];
int f[110][N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main()
{
cin>>n;
int d=0;
for(int i=1;i<=n;i++){
cin>>w[i];
d=gcd(d,w[i]);
}
if(d!=1)
cout<<"INF";
else{
for(int i=0;i<=n;i++)
f[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<N;j++){
f[i][j]=f[i-1][j];
if(j>=w[i])
f[i][j]+=f[i][j-w[i]];
}
}
int cnt=0;
for(int j=1;j<N;j++){
if(!f[n][j])
cnt++;
}
cout<<cnt;
}
return 0;
}
💬 评论