Twice Equation（递推+java大数）

90 阅读 0 评论 60 点赞

我是靠谱客的博主外向小虾米，最近开发中收集的这篇文章主要介绍Twice Equation（递推+java大数），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题 L: Twice Equation

题目描述

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

输入

This problem contains multiple test cases. The first line of a multiple input is an integer T (1 ≤ T < 1000) followed by T input lines. Each line contains an integer L (1 ≤ L < 10¹⁹⁰ ).

输出

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

样例输入

样例输出

3
20
119

先用的c++打出前几项然后找出了一个递推的规律fn=f(n-1)*6-f(n-2)+2，然后就是直接用java大数直接while模拟递推就可以。

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int t;
t=cin.nextInt();
while (t--!=0){
BigInteger n,a,b,c;
n=cin.nextBigInteger();
if(n.compareTo(BigInteger.valueOf(3))<=0) {
System.out.println("3");
continue;
}
if(n.compareTo(BigInteger.valueOf(20))<=0) {
System.out.println("20");
continue;
}
a=BigInteger.valueOf(3);
b=BigInteger.valueOf(20);
while(true) {
c=b.multiply(BigInteger.valueOf(6)).subtract(a).add(BigInteger.valueOf(2));
if(c.compareTo(n)>=0) {
System.out.println(c);
break;
}
a=b;
b=c;
}
}
}
}