ICPC Asia Nanning 2017 L. 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

Sample Output

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);

        }

    }

}

巴特西

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

Description

Input

Output

Sample Input

Sample Output

Solution

题意

题解

Code

最新文章

热门文章

巴特西

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

Description

Input

Output

Sample Input

Sample Output

Solution

题意

题解

Code

最新文章

热门文章

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