//注意到整个表中无论横竖，总是单调的。
//所以可以利用二重二分，时间复杂度 O(n*(log n)^2)
//第二重二分选择行或者列来进行都可以。请注意列是递增，行是递减
import java.util.*;
public class Main{
	static int N;
	static long M;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int T = s.nextInt();
		while(T-->0){			
			N = s.nextInt();
			M = s.nextLong();
			
//                      设定第一重二分的上下界
			long l = -25000000001l;
			long r =  25000000001l;
			
			while(r-l>1){
				long m = (l+r)/2;
//                              检验该m是否符合条件
				if(check(m)){
					r = m;
				}else{
					l = m;
				}
			}
			System.out.println(r);
		}
	}
	
	private static boolean check(long m) {
//              计算各列中共有多少个值小于等于m，并加在一起
//              然后判断该总数与M的大小关系
		long count = 0;
		for(int i = 1; i <= N;i++){
//                      对表格中的每列进行一次二分，找出该列有多少个数小于等于m并加入count
//                      也就是说每进行一次第一重二分，都要进行N次第二重二分
			count += binary(i,m);
		}
		if(count >= M){
			return true;
		}else{
			return false;
		}		
	}

	private static long binary(long i, long m) {
//              对表格中的每列进行一次二分，找出该列有多少个数小于等于m
		long lb = 0;
		long rb = N+1;
		while(rb - lb > 1){
			long mb = (lb+rb)/2;
			long ji = mb*mb + i*i + 100000*mb - 100000*i + mb*i;

			if(ji <= m){
				lb = mb;
			}else{
				rb = mb;
			}
		}
//              返回该行小于等于m的数的个数
		return lb;
	}

}

• 感谢，终于知道了我WA是因为上下界设得太小 (22) ksqsf 2017-12-12 19:41:18