POJ.3685 Matrix

1.Problem
http://poj.org/problem?id=3685

2.Idea
Binary Search + Binary Search

3.Source

 #define MAX_N 50010  
 ll N, M;  
 ll getVal(ll i, ll j)  
 {  
      return i*i + 100000 * i + j * j - 100000 * j + i * j;  
 }  
 bool C(ll x)  
 {  
      ll cnt = 0;  
      for (ll j = 1LL; j <= N; j++) {  
           ll l = 0;  
           ll r = N + 1;  
           while (r - l > 1) {  
                ll m = (l + r) / 2;  
                if (getVal(m, j) < x) {  
                     l = m;  
                }  
                else {  
                     r = m;  
                }  
           }  
           cnt += l;  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      ll r = MAX_N * MAX_N * 3 + MAX_N * 100000 * 2;  
      ll l = -r;  
      while(r - l > 1) {  
           ll m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%lld\n", l);  
 }  
 int main()  
 {  
      int t;  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%lld%lld", &N, &M);  
           solve();  
      }  
      return 0;  
 }