Description

Given a N × N matrix A, whose element in the i-th row and j-th column A_ij is an number that equals i² + 100000 × i + j² - 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

121 12 12 22 32 43 13 23 83 95 15 255 10
Sample Output
3-99993312100007-199987-99993100019200013-399969400031-99939
題意：給了一個(gè)N*N的矩陣，每個(gè)位置上的數(shù)由該位置的下標(biāo)i,j決定。然后問這個(gè)矩陣中第m小的數(shù)。
思路：第一個(gè)二分枚舉答案，然后就要判斷這個(gè)數(shù)前面有幾個(gè)數(shù)，他是不是第m個(gè)數(shù)，如果n*n枚舉肯定炸，通過公式可知，函數(shù)跟j不是單調(diào)的關(guān)系，但跟i是單調(diào)的關(guān)系，所以每次枚舉j，然后二分i的值，然后看前面有幾個(gè)比第一個(gè)二分小的數(shù)，總的復(fù)雜度就是n*lgn*lgn。
小結(jié)：我一開始有個(gè)疑問，第2個(gè)二分判斷的是前面有幾個(gè)數(shù)比mid小，萬一前面又m-1個(gè)數(shù)比他小，這樣二分的這個(gè)數(shù)就是第m大了，可是如果這個(gè)mid并不在矩陣?yán)镎k。。。其實(shí)第一個(gè)二分的跳出條件是num >= m，如果第一個(gè)二分枚舉的mid 是第m大，return 0，然后mid變大，又在后面的區(qū)間二分，如果前面有m個(gè)數(shù)，但是這個(gè)數(shù)大于矩陣?yán)锏牡趍個(gè)數(shù)，mid就會變小，然后就不斷逼近矩陣?yán)锏牡趍個(gè)數(shù)，l慢慢變大，r慢慢變小，最后一次是第二個(gè)二分返回m個(gè)數(shù)，并且最后一個(gè)數(shù)就是第一個(gè)二分的mid。。
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int maxn = 5e4 + 5;typedef long long ll;ll n, m;ll cnt(ll i, ll j){    return i*i + 100000*i + j*j - 100000*j+i*j;}int check(ll x){    ll num = 0;    for(ll j = 1; j <= n; j++)    {        ll l = 1, r = n, mid, ans = 0;        while(l <= r)        {            mid = (l+r)/2;            if(cnt(mid, j) <= x)  //這里要有等號            {                ans = mid;                l = mid + 1;            }            else            {                r = mid - 1;            }        }        num += ans;        if(num >= m) return 1;  //這里也要有等號    }    return 0;}int main(){    int t;    scanf("%d", &t);    while(t--)    {        scanf("%lld%lld", &n, &m);        ll l = -(ll)100000*n, r = n*n+(ll)100000*n+n*n+n*n, mid, ans;        while(l <= r)        {            mid = (l+r)/2;            if(check(mid))            {                ans = mid;                r = mid - 1;            }            else                l = mid + 1;        }        PRintf("%lld/n", ans);    }    return 0;}