2022 Henan Mengxin League game (3): Henan University a - corn cannon

A - Cob Cannon

It is easy to find that the answer is monotonous , If it costs x Time can defeat the target , It costs $x+1$ Time can also defeat the target , You can directly split the answer , Considering that the left and right range of two points is $[0,10^{18}]$, about C + + Contestants may need to use __int128 , Or judge in advance whether it is legal in the process of dichotomy .

• Time complexity $O(n\times log(10^{18}))$

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

typedef long long LL;
const int N = 100010;

int a[N],b[N];
int n,m;

int check(LL x)
{
    
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
    
		sum+=(x/b[i]+1)*a[i];
		if(sum>=m) return 1;
	}
	return 0;
}

int main()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	LL l=0,r=1e18;
	while(l<r)
	{
    
		LL mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}