·【蓝桥】·包子凑数

题目来源：·【Acwing】·包子凑数
典型的Ax+By=C问题，另一篇博客有详细总结：Ax+By=C的解的讨论(仅A,B为常数)

问题描述
　　小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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
4
6
样例输出
INF
样例说明
　　对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
　　对于样例2，所有奇数都凑不出来，所以有无限多个。

题目分析

  • 依据另一篇博客中有关Ax+By=C的解的讨论(仅A,B为常数)，Ax+By=C可推广到：$a_0x_0+a_1x_1+…+a_{n-1}x_{n-1} = c$
  1. 若$a_0,a_1,…a_{n-1}$ 不互质，则无解的C的个数为INF。
  2. 反之，无解的C的个数有限，C最大取$max{C|C导致无解} = a_0a_1…*a_{n-1} - (a_0+a_1+…+a_{n-1})$，输入条件得，这个max是小于10000的。
    —————————————先上主函数—————————————
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int n;
    int a[105];
    bool b[10005];
    int gcd(int a, int b){
    	return b ? gcd(b,a%b) : a;
    }
    int main(){
    	scanf("%d", &n);
    	for(int i = 0 ; i < n; ++i){
    		scanf("%d", &a[i]);
    	}
    	int g = 0;
    	for(int i = 0; i < n; ++i){
    		g = gcd(g, a[i]);
    	}
    	if(g == 1){		//互质，则有确定无解的个数
    		solve();
    	}else{
    		printf("INF\n");
    	}
    	return 0;
    }

接下来主要是讨论互质条件下如何确定C无解的个数
算法思想

  1. 其实就是个完全背包，可选的物品的个数很多，看能不能凑成C，
    但不涉及到背包价值，没必要套dp；
  2. 类似埃式筛素数的算法，已经确定了C的范围（0，10000），定义一个数组num[]，范围最大自然就是10000了；
  3. 如果mum[j]能凑成C，显然num[j + a[i]]能凑成C，筛的时候注意i 和 j循环的先后。
    ————————————————————————————————————
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void solve(){
    	int ans = 0;
    	b[0] = true;
    	for(int i = 0; i < n; ++i){
    		for(int j = 0; j+a[i] < 10005; ++j){
    			if(b[j]){
    				b[j+a[i]] = true;
    			}
    		}
    	}
    	for(int i = 1; i < 10005; ++i){
    		if(!b[i]){
    			ans++;
    		}
    	}
    	printf("%d\n", ans);
    }

———————更新失败，看后续还能不能想出其他方法