长方形切正方形公式

//经典二分模板+知识点：a*b的长方形可切成(a/c)*(b/c)个的边长为c的正方形
//原题：https://www.acwing.com/problem/content/1229/

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;

int n,k;
int h[N],w[N];

bool check(int a){
    int num=0;

    for(int i=0;i<n;i++)
    {
        num+=(w[i]/a)*(h[i]/a);
        if(num>=k) return true;
    }

    return false;
}

int main(){
    cin>>n>>k;

    for(int i=0;i<n;i++)
    {
        cin>>h[i]>>w[i];
    }

    int l=1,r=1e5;
    while(l<r)
    {
        int mid=l+r+1>>1;

        if(check(mid))
        {
            l=mid;
        }else
        {
            r=mid-1;
        }
    }

    cout<<l;
    return 0;
}