题解 | #一生之敌#

考察数论和二分查找，因为n比较大，要开BigInteger。

要使b^2 = 2 * a * (a + 1)^2,

设a = 2 * k^2,

则b = 4 * k^3 + 2 * k。

让b = 10^19,

解得：k = 2 * 10^6。

所以每次二分查找k的范围为[0,2000000],求第一个4 * k^3 + 2 * k >= n。

import java.util.Scanner;

import java.math.BigInteger;

public class Main {

static BigInteger four = BigInteger.valueOf(4);
static BigInteger two = BigInteger.valueOf(2);
// sum()计算 4*k^3 + 2*k
// 使用 BigInteger 防止计算结果超过 9.2 * 10^18 (Java long 的上限)
public static BigInteger sum(long k) {
    BigInteger big = BigInteger.valueOf(k);
    // 4 * k^3 + 2 * k
    return four.multiply(big).multiply(big).multiply(big).add(big.multiply(two));
}

// 二分查找第一个 >= n 的值
public static BigInteger erfen(BigInteger n) {
    long l = 0;
    long r = 2000000;
    BigInteger ans = BigInteger.valueOf(0);
    while (l <= r) {
        long mid = (l + r) / 2;
        BigInteger m = sum(mid);

        if (m.compareTo(n) >= 0) {
        	ans = m;
            r = mid - 1;
        } 
        else {
            l = mid + 1;
        }
    }
    return ans;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    while (scan.hasNextInt()) {
        int T = scan.nextInt();
        for (int i = 1; i <= T; i++) {
			BigInteger n = scan.nextBigInteger();
			System.out.println(erfen(n));
		}
    }
    scan.close();
}

}