L. Twice Equation （ICPC Asia Nanning 2017题解）

题意：根据公式2*m*(m+1)==n*(n+1),要求n>=L(1<=L<=1e190),m是任意值，找出一个满足条件的n。

思路：L的范围非常大，但是通过找满足条件的数据却非常少，我是先暴力求出前1e4满足条件的数，发现有3,20,119,696,4059……。发现一个规律，如果放到数组中就是a[i]=a[i-1]*6-a[i-2]+2。但是数组可能开不了，所以我们每一次都算一下。1e190大概就是6的300次方。

INPUT
3
1
4
21
OUTPUT
3
20
119

AC代码：

import java.math.*;
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int t;
t=cin.nextInt();
while(t > 0) {
t--;
BigInteger n;
n = cin.nextBigInteger();
BigInteger p = new BigInteger ("0");
BigInteger q = new BigInteger ("3");
BigInteger six = new BigInteger ("6");
BigInteger two = new BigInteger ("2");
BigInteger tmp;
if(n.compareTo(q) <= 0) {
System.out.println("3");
}
else {
for(int i=1;i<=500;i++) {
tmp =q;
q = q.multiply(six).subtract(p).add(two);
p = tmp;
if(q.compareTo(n) >= 0) {
System.out.println(q);
break;
}
}
}
}
cin.close();
}
}

最后

以上就是危机发夹为你收集整理的L. Twice Equation （ICPC Asia Nanning 2017题解）的全部内容，希望文章能够帮你解决L. Twice Equation （ICPC Asia Nanning 2017题解）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。