二分法，分。巧。克。力，数论，gcd，方程的解，状态dp，包。子。凑。数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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，所有奇数都凑不出来，所以有无限多个。

　　资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms


　　请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

　　注意：
　　main函数需要返回0;
　　只使用ANSI C/ANSI C++ 标准;
　　不要调用依赖于编译环境或操作系统的特殊函数。
　　所有依赖的函数必须明确地在源文件中 #include
　　不能通过工程设置而省略常用头文件。

　　提交程序时，注意选择所期望的语言类型和编译器类型。

本题不会写，暴力枚举也没有思路，暴力枚举下面这个链接可以ac，但是显然，全是奇数时不应该输出INF，蓝桥杯历届试题 包子凑数 (暴力)_Suprit的博客-CSDN博客_蓝桥杯包子凑数历届试题 包子凑数 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加...https://blog.csdn.net/a1097304791/article/details/88562194?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164847181616782184695765%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164847181616782184695765&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-88562194.142^v5^pc_search_result_cache,143^v6^register&utm_term=%E5%8C%85%E5%AD%90%E5%87%91%E6%95%B0baoli&spm=1018.2226.3001.4187

 还是看看标准的解答

首先说一下，我感觉这是一道多元一次方程的题，可是下面就没有思路了

真题解析│蓝桥杯省赛真题之包子凑数_整数

上面链接思路比较清晰

#include 
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const LL maxn = 13000;
int n;
int a[maxn];
int dp[maxn] = {0};
int gcd(int a,int b){
	while(a!=b){
		if(a>b)
		    a = a - b;
		else
		    b = b - a;
	}
	return a;
}
int main(){
	cin>>n;
	for(int i = 1;i <= n;i++)
	    cin>>a[i];
	int g = a[1];
	for(int i = 2;i <= n;i++)
	{
		//cout<<__gcd(g,a[i])< 
 
分巧克力
 
比较简单，当时学二分的时候，容易看出，现在反而没有看出来
 
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
 　　小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。

 　　为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

 　　1. 形状是正方形，边长是整数
 　　2. 大小相同

 　　例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

 　　当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
 
输入格式
 
　　第一行包含两个整数N和K。(1 <= N, K <= 100000)
 　　以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
 　　输入保证每位小朋友至少能获得一块1x1的巧克力。
 
输出格式
 
　　输出切出的正方形巧克力最大可能的边长。
 
样例输入
 
2 10
 6 5
 5 6
 
样例输出
 
2

 资源约定：
 峰值内存消耗（含虚拟机） < 256M
 CPU消耗 < 1000ms


 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

 注意：
 main函数需要返回0;
 只使用ANSI C/ANSI C++ 标准;
 不要调用依赖于编译环境或操作系统的特殊函数。
 所有依赖的函数必须明确地在源文件中 #include 
 不能通过工程设置而省略常用头文件。

 提交程序时，注意选择所期望的语言类型和编译器类型。
 
二分，直接套用即可
 
#include 
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const LL maxn = 130000;
int n;
int k;
int h[maxn],w[maxn];
int gcd(int a,int b){
	while(a!=b){
		if(a>b)
		    a = a - b;
		else
		    b = b - a;
	}
	return a;
}
bool check(int m){
	int counts = 0;
	for(int i = 1;i <= n;i++)
        {
        	counts += (h[i]/m)*(w[i]/m);
        }
    return counts>=k;//等于
}
int main(){
	cin>>n>>k;
	int maxsize = 0;
	for(int i = 1;i <= n;i++){
		cin>>h[i]>>w[i];
		maxsize = max(h[i],maxsize);
		maxsize = max(w[i],maxsize);
	}
	int le = 1,ri = maxsize;
	int mid,ans = 1;
	while(le<=ri){//等于
		mid = le+(ri-le)/2;
		if(check(mid))
		    {
		    	le = mid+1;
		    	ans = mid;/记录答案
		    }
		else
		    ri = mid-1;
	}
	cout<