【HDOJ6222】Heron and His Triangle（Java，二分，递推）

题意：让你找这样的一个三角形，三条边为t，t-1，t+1，并且面积为整数，最后满足t大于等于n。

n<=1e30

思路：直接推式子不会，打表找规律

f(n)=4*f(n-1)-f(n-2）(n>=3)

f(1)=4 f(2)=14

队友用Java写的，再写个二分就行

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


public class Main {    
     public static void main(String[] args){
         int t;
         BigInteger[] a = new BigInteger[110];
         BigInteger n;
         Scanner sc = new Scanner(System.in);
         //System.out.println(new BigInteger("11").compareTo(new BigInteger("9")));
         a[1] = new BigInteger("4");
         a[2] = new BigInteger("14");
         a[3] = new BigInteger("52");
         for(int j = 4; j <= 100; ++j){
             a[j] = a[j - 1].multiply(new BigInteger("4")).subtract(a[j - 2]);
         }
         t = sc.nextInt();
         for(int i = 1; i <= t; ++i){
             n = sc.nextBigInteger();
             //System.out.println(n);
             for(int j = 1; j <= 100; ++j){
                 if(a[j].compareTo(n) >= 0){
                     System.out.println(a[j]);
                     break;
                 }
             }
         }
     }