ICPC Asia Nanning 2017 L. Twice Equation (规律 高精度运算)

题目链接：Twice Equation

比赛链接：ICPC Asia Nanning 2017

Description

For given \(L\), find the smallest \(n\) no smaller than \(L\) for which there exists an positive integer \(m\) for which \(2m(m + 1) = n(n + 1)\).

Input

This problem contains multiple test cases. The first line of a multiple input is an integer \(T (1 \le T < 1000)\) followed by \(T\) input lines. Each line contains an integer \(L (1 \le L < 10^{190})\).

Output

For each given \(L\), output the smallest \(n\). If available nn does not exist, output \(−1\).

Sample Input

3
1
4
21

Sample Output

3
20
119

Solution

题意

给出一个整数 \(L\)，求大于等于 \(L\) 的最小整数 \(n\) 满足存在一个整数 \(m\) 使得 \(2m(m + 1) = n(n + 1)\)。

题解

打表找规律

\[f(n) = f(n - 1) * 6 - f(n - 2) + 2\]

然后用 Java 大数求解即可。

Code

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger[] a = new BigInteger[1000];
        // 打表
        a[0] = BigInteger.ZERO;
        a[1] = BigInteger.valueOf(3);
        BigInteger six = new BigInteger("6");
        BigInteger two = new BigInteger("2");
        for(int i = 2; i < 300; ++i) {
            a[i] = ((a[i - 1].multiply(six)).subtract(a[i - 2])).add(two);
        }

        int t = in.nextInt();
        while (t-->0){
            boolean flag = false;
            BigInteger l = in.nextBigInteger();
            for(int i = 0; i < 1000; ++i) {
                if(a[i].compareTo(l) >= 0) {
                    System.out.println(a[i]);
                    flag = true;
                    break;
                }
            }
            if(!flag) System.out.println(-1);
        }
    }
}