POJ3685(二分套二分)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define INF 1e9+7
typedef long long ll;

ll maxn, m;  //如果用int会WA,我也不知道为什么
ll Sum(ll x, ll y)
{
    ll ans = x*x + 100000 * x + y*y - 100000 * y + x*y;
    return ans;
}

ll Binarysearch(ll x)
{
    ll sum = 0;
    for (ll j = 1; j <= maxn; j++) {
        int lb = 0, rb = maxn + 1;
        while (rb - lb >1) {
            ll mid = (lb + rb) / 2;
            if ( Sum(mid, j) < x) lb = mid;
            else rb = mid;
        }
        sum += (rb - 1);
    }

    return sum;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%lld", &maxn, &m);
        ll rb = 1e12, lb = -1e12;
        while (rb - lb > 1) {
            ll mid = (lb + rb) / 2;
            if (Binarysearch(mid) < m) lb = mid;
            else rb = mid;
        }
        printf("%lld\n", rb - 1);
    }


    return 0;
}