F - Heron and His Triangle HDU - 6222

A triangle is a Heron’s triangle if it satisfies that the side lengths of it are consecutive integers t-1, t, t+ 1 and thatits area is an integer. Now, for given n you need to find a Heron’s triangle associated with the smallest t bigger
than or equal to n.
Input
The input contains multiple test cases. The first line of a multiple input is an integer T (1 ≤ T ≤ 30000) followedby T lines. Each line contains an integer N (1 ≤ N ≤ 10^30).
Output
For each test case, output the smallest t in a line. If the Heron’s triangle required does not exist, output -1.
Sample Input
4
1
2
3
4
Sample Output
4
4
4
4

• 题意:给你一个n,在t>=n的范围内求一个数t.使得t-1,t,t+1所组成的三角形面接为整数.

• 解题思路:打一个表,发现递增的很快,并且递归方程为s[n]=4*s[n-1]-s[n-2].由于数据太大,因此用java大数表示.

import java.math.BigInteger;
import java.math.*;
import java.util.Scanner;
public class Main {
       public static void main(String[] args) {
       Scanner input = new Scanner(System.in);BigInteger []m=new BigInteger[60];m[0]=BigInteger.valueOf(2);m[1]=BigInteger.valueOf(4);for(int i=2;i<60;i++) {
       m[i]=m[i-1].multiply(BigInteger.valueOf(4)).subtract(m[i-2]);}int t;t=input.nextInt();for(int j=0;j<t;j++){
       BigInteger h;h=input.nextBigInteger();for(int i=1;i<60;i++) {
       if(m[i].compareTo(h)>=0) {
       System.out.println(m[i]);break;}}}}
}