分巧克力（蓝桥杯，二分，acwing）

题目描述：

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi的方格组成的长方形。

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

切出的巧克力需要满足：

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

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式：

第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式：

输出切出的正方形巧克力最大可能的边长。

数据范围：

1≤N,K≤1e5,

1≤Hi,Wi≤1e5

输入样例：

2 10
6 5
5 6

输出样例：

2

分析步骤：

  第一：理清思路，：

1. 我们拿到这个题目，我们先考虑怎么满足第一个条件怎么保证他是正方形呢？正方形得保证相邻的两条边一定得是相等的，我们可以拿长和宽去除以一个数得到的数相乘就代表着这是我们最多可以求出的正方形数。例如一个长和宽分别是10和20的纸板，我们要求出它最多可以有多少个2x2的纸板。只需要拿(长去除以2的商)乘上(宽去除以2的商)-->5x10=50个。这就是我们推出的数学公式，这是本题的第一个特点。

2. 题目中要我们求的是最值，那么就代表着我们可以找到一个点，在这个点的左边是符合条件的，在这个点的右边不符合条件，这就是最值的特点。我们还可以发现这个序列一定是递增的，从小到大看看那个值是符合条件的。所以即是单调又是最值，那么就符合我们的二分的算法条件，我们就使用二分算法，这是本题的第二个特点。

  第二：书写主函数，构建整体框架：

1. 我们可以用pair和这个结构，将长和宽放到一个点的位置上。

2. 我们定义左边界为1，右边界为1e5。我们的左右边界一定是极端情况的答案，只有把极端情况也包含进来了的话，那么才不会漏掉答案。l为1是因为长和宽最小是1，所以当真的为1时而且只有一个人的时候我们就只能输出1个1x1的巧克力了；r为1e5是因为长和宽最大是1e5，所以当真的为1e5时且只有一个人的时候最大就是1e5。这就是两个极端情况。

3. 进入我们的while循环只要l>n>>m; for(int i = 0 ; i >q[i].x>>q[i].y; } int l = 1 , r = 1e5; while(l>m; for(int i = 0 ; i >q[i].x>>q[i].y; } int l = 1 , r = 1e5; while(l