# 分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。  

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

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

* 形状是正方形，边长是整数

* 大小相同

例如一块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
```

以下选项<span style="color:red">错误</span>的是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}
int main()
{
    int n, k;
    vector<pair<int, int>> vec;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int h, w;
        cin >> h >> w;
        if (h > w)
        {
            int temp = h;
            h = w;
            w = temp;
        }
        vec.push_back(pair<int, int>(h, w));
    }
    sort(vec.begin(), vec.end(), cmp);
    int s = vec[0].first;
    while (s)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            int h = vec[i].first;
            int w = vec[i].second;
            if (s > h || s > w)
                break;
            sum += (h / s) * (w / s);
        }
        if (sum >= k)
            s--;
    }
    cout << s;
    return 0;
}
```
## 选项


### A

```c
int main()
{
    int n, k;
    int h[100000];
    int w[100000];
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i] >> w[i];
    }
    int len = 100000;
    for (; len >= 1; len--)
    {
        int cnt = 0;

        for (int i = 0; i < n; i++)
        {
            cnt += (h[i] / len) * (w[i] / len);
        }
        if (cnt >= k)
        {
            cout << len << endl;
            return 0;
        }
    }
    return 0;
}
```

### B

```c
typedef struct
{
    int h, w;
} node;
const int maxn = 1e5 + 7;
node a[maxn];
int n, k, mx = -1;
bool check(int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cnt += (a[i].h / x) * (a[i].w / x);
    }
    if (cnt >= k)
        return true;
    else
        return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].h, &a[i].w);
        if (a[i].w > mx)
            mx = a[i].w;
        if (a[i].h > mx)
            mx = a[i].h;
    }

    int l = 1, r = mx, ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}
```

### C

```c
int co[100100][2];

int coun(int n, int x)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += (co[i][0] / x) * (co[i][1] / x);
    }
    return sum;
}

int binary(int n, int k)
{
    int l = 0, r = 100000;
    while (l < r)
    {
        int mid = (r - l) / 2 + l;
        if (coun(n, mid) < k)
            r = mid - 1;
        else if (coun(n, mid) > k)
            l = mid + 1;
        else
            return mid;
    }
    return r;
}

int main()
{
    int n;
    int k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &co[i][0], &co[i][1]);
    printf("%d\n", binary(n, k));
}
```