题目描述

Given a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.

Input

The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.

Output

For each test case output the answer on a single line.

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

解题思路：
通过分析已知的方程我们知道：该方程在j固定而i增大时增大，而i固定j增大时就不一定了，那么我们就按列遍历，设定一个x，我们统计每一列中<=x的数的个数，即查找这一列中这个数x的lower_bound，然后我们把他们加起来与目标m进行比较，以此为判断条件对x进行二分。

试想，我现在有一个x，然后我看看每一列有多少个小于等于x的数，把他们加起来就是矩阵中小于等于x的数的个数，我们要求的是矩阵中第m小的数，也就是说如果这个数是x，那么矩阵中有m个小于等于x的数(当然最大的那个要是x)，这样我们就可以二分x，让他逼近矩阵中有m个小于等于x的数这个条件，直至求出x。

AC代码：

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <vector>
#include <bitset>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const long long LINF = 1e14;
const double PI = acos(-1.0);
const int MAXN = 3e5+10;

ll n, m;

ll f(ll x, ll y)
{
    return x*x + y*y + x*y + 100000*(x - y);
}

bool judge(ll x) //判断矩阵中<=x的数的个数是否>=m
{
    ll res = 0;
    for(int i = 1; i <= n; i++) //按列遍历
    {
        int low = 0, up = n + 1;
        while(up - low > 1)
        {
            int mid = (up + low) / 2;
            if(f((ll)mid, (ll)i) >= x) up = mid;
            else low = mid;
        }
        res += low; //把每一列<=x的数的个数加起来
    }
    return res >= m;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        scanf("%lld%lld", &n, &m);
        ll low = -LINF, up = LINF;
        while(up - low > 1)
        {
            ll mid = (up + low) >> 1;
            if(judge(mid)) up = mid;
            else low = mid;
        }
        printf("%lld\n", low);
    }
    return 0;
}