当前位置: 首页 > >

2017ACM/ICPC沈阳 F

发布时间:

博客目录


原题

题目传送门


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使得:t>=n


且以长度为t-1 ,t ,t+1的三条边构成的三角形面积为整数。


输出t。


规律:打表可得在2e7范围内满足上述条件的t有


?4,14,52,194,724,2702,10084,37634


然后有 t[i]=4*t[i-1]-t[i-2];


然后菜鸡现学现卖java大数(因为这一场有个签到题是自己手写的大数加法,然后用c++写了半天发现要改成减法还是要费一段功夫,就有点怂换java)


AC代码

//package learn1;


import java.util.*;
import java.math.*;
public class Main {
?? ?public static BigInteger co[]=new BigInteger[200];
?? ?public static void main(String[] args) {
?? ??? ?// TODO 自动生成的方法存根
?? ??? ?Scanner cin = new Scanner(System.in);
?? ??? ?int T;
?? ??? ?T=cin.nextInt();
?? ??? ?BigInteger n; // 4,14,52,194,724,2702,10084,37634
?? ??? ?co[0]=new BigInteger("4");//("4");
?? ??? ?co[1]=new BigInteger("14");
?? ??? ?for(int i=2;i<=180;i++){? //我们发现第180多个已经很大很大够用了。
?? ??? ??? ?co[i]=co[i-1].multiply(co[0]);
?? ??? ??? ?co[i]=co[i].subtract(co[i-2]);
?? ??? ?}
?? ??? ?while(T-->0){
?? ??? ??? ?n=cin.nextBigInteger();
?? ??? ??? ?for(int i=0;;i++){
?? ??? ??? ??? ?if(n.compareTo(co[i])<=0){
?? ??? ??? ??? ??? ?System.out.println(co[i].toString());
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}


}
?




友情链接: