Descriptions

有一个N阶方阵 第i行,j列的值$A_{ij} =i^2 + 100000 × i + j^2 – 100000 × j + i×j$,需要找出这个方阵的第M小值.

Input

第一行输入T代表测试组数.
每个测试用例包含2个数字N,M表示在N阶方阵找出第M大值, N(1 ≤ N ≤ 50,000) and M(1 ≤ M≤ N × N). 每两个测试用例之间可能有空行

Output

输出方阵的第M小值

Sample Input

12
1 1
2 1
2 2
2 3
2 4
3 1
3 2
3 8
3 9
5 1
5 25
5 10

Sample Output

3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939

题解 (二分套二分)

观察$i^2 + 100000 × i + j^2 – 100000 × j + i×j$这个表达式，发现是对i递增的，于是利用这个特性，二分统计每一列比mid小的数的个数的总和，如果总和大于等于k，说明右端点过大，否则左端点过小。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;

LL n,k;

LL f(LL i,LL j)
{
    return i*i+100000*i+j*j-j*100000+i*j;
}

LL check(LL x)
{
    LL cnt=0;
    for(int j=1;j<=n;j++)//枚举列，二分找出比mid小的个数
    {
        int l=0,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(f(mid,j) <= x) l=mid;
            else r=mid-1;
        }
        cnt+=l;
    }
    //cout<<"---"<<x<<' '<<cnt<<endl;
    return cnt;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>k;

        LL l=-100000*n,r=n*n+100000*n+n*n+n*n;
        while(l<r)
        {
            LL mid=l+r>>1;
            if(check(mid) >= k) r=mid;
            else l=mid+1;
        }

        cout<<l<<endl;
    }
    //system("pause");
}