典型的整数二分
一般的情况左边放的数是成立的数据,右边是不成立
由于本题找的是最大成立的条件所以我们要左边的答案
所以整数二分向下取整就可以了。
#include<iostream>
using namespace std;
const int N= 1e5;
int a[N],b[N];
int main(){
int n,m;cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
int l=1,r=N,mid;
while(r>l){
mid=l+r+1 >>1;
long long cnt=0;
for(int i=0;i<n;i++) cnt+=1ll*a[i]/mid*(b[i]/mid);
if(cnt>=m) l=mid;
else r=mid-1;
}
cout<<r<<endl;
}