I am trying to solve this problem, facing probably an overflow issue.

Here's my code:

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define NL cout<<"\n";

typedef long long int lli;

void Solve(){
	lli w, h, n; cin >> w >> h >> n;
	lli l=1, r = (sqrt(n)+1)*(max(w,h)), mid;
	while (l + 1 < r) {
		mid = l + (r-l)/2;
		if ((mid/w) *(mid/h) > n) {
			r = mid;
		} else {
			l = mid;
		}
	}
	// cout << l << ", " << r;NL
	if ((l/w)*(l/h) == n) {
		cout << l;NL;
	} else {
		cout << r;NL;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	lli t;
	// cin >> t;
	t=1;
	for (int i=0; i<t; ++i) { Solve();}
	return 0;
}

I am sure there's an overflow issue but I have one more doubt. After being unsuccessful after many attempts, I started reading comments under the problems and found a guy who posted his working solution as:

#include<bits/stdc++.h>
#define ll long long

using namespace std;
int main(){
	unsigned ll a, b, n;
	cin >> a >> b >> n;
	unsigned ll l = 0, r = 1e18;

	while(r > l+1){

		unsigned ll m = (l+r)/2;
		if((m/a)*(m/b) >= n){
			r = m;
		}
		else l = m;
	}
	cout << r;
}

I read his code and found he didn't do anything for the overflow issue except use an unsigned data type. I submitted his code just to see if it works but it failed in the $$$27^{th}$$$ test case (Mine was failing in the $$$5^{th}$$$ test case). So I thought I should try my code with unsigned long long, and therefore I did, here's the code:

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define NL cout<<"\n";

#define ll long long

void Solve(){
	unsigned ll w, h, n; cin >> w >> h >> n;
	unsigned ll l=0, r = 1e18, mid;
	while (l + 1 < r) {
		mid = l + (r-l)/2;
		if ((mid/w) *(mid/h) > n) {
			r = mid;
		} else {
			l = mid;
		}
	}
	// cout << l << ", " << r;NL
	if ((l/w)*(l/h) >= n) {
		cout << l;NL;
	} else {
		cout << r;NL;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	// cin >> t;
	t=1;
	for (int i=0; i<t; ++i) { Solve();}
	return 0;
}

But still my code failed on $$$5^{th}$$$ test case only. That makes me doubt my binary search algorithm.

I have tried to maintain the following invariants: $$$f(l) <= n$$$, and $$$f(r) > n$$$, throughout the binary search loop, and then at the end I check if $$$f(l) == n$$$ or not if yes then return $$$l$$$ otherwise $$$r$$$.

I have also tried using double, and using logarithms for the comparison but it didn't work. I tried $$$ log(mid/w) + log(mid/h) > n $$$, don't know why this shouldn't work, would appreciate your views on this.

Please have a look at my binary search algo and see if it is correct. Also, it would be great if you give me some hint on how to avoid overflow. I have really spent a lot of time on this problem (which is very straightforward except for the overflow part), so your help would be really appreciated.

Thanks a lot! May you have a wonderful day!