检查一个数字是否为斐波纳契序列？

Question

它被要求找到一种方法来检查一个数字是否在斐波纳契序列中。约束条件是

1≤T≤10^5

1≤N≤10^10

当T是测试用例的数量时，

N是给定的数，Fibonacci候选被测试。

我用一个数字是Fibonacci的事实写它的当且仅当(5*n2 + 4)或(5*n2-4)中的一个或两者都是一个完美的平方:-

import java.io.*;
import java.util.*;

public class Solution {

 public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    for(int i = 0 ; i < n; i++){
        int cand = sc.nextInt();
        if(cand < 0){System.out.println("IsNotFibo"); return; }
        int aTest =(5 * (cand *cand)) + 4;
        int bTest = (5 * (cand *cand)) - 4;
        int sqrt1 = (int)Math.sqrt(aTest);// Taking square root of aTest, taking into account only the integer part.
        int sqrt2 = (int)Math.sqrt(bTest);// Taking square root of bTest, taking into account only the integer part.
        if((sqrt1 * sqrt1 == aTest)||(sqrt2 * sqrt2 == bTest)){
            System.out.println("IsFibo");
        }else{
            System.out.println("IsNotFibo");
        }
       }
     }
  }

但它没有清理所有的测试用例？我能做什么bug修复？

Answer 1

根据这链接，一个数字是Fibonacci当且仅当(5*n2 + 4)或(5*n2 - 4)中的一个或两者都是完美的平方，所以基本上可以这样做。

希望这会有所帮助:)

Answer 2

对每个测试用例使用二进制搜索和Fibonacci q-矩阵解决方案，如果您使用平方幂的话。

您的解决方案不起作用，因为它需要舍入大型数字的浮点平方根(可能足够大，甚至不适合于long)，这有时并不准确。

二进制搜索的工作方式如下:查找Q^m：如果m-th Fibonacci数大于您的值，则设置right = m，如果是相等的返回true，则设置left = m + 1。

Answer 3

正如人们正确地说的，平方米可以四舍五入。所以：

• 即使使用long而不是int，它也有18位数字。
• 即使您使用的是Math.round()，而不是简单的(int)或(long)。请注意，由于这个原因，您的函数即使在较小的数字上也不能正常工作。

双位有14位，长有18位，所以你不能用正方形，你需要20位。

BigInteger和BigDecimal没有sqrt()函数。

所以，你有三种方法：

• 为BigInteger编写自己的sqrt。
• 检查发现的不精确的double sqrt()周围的所有数字是否是一个真实的sqrt。这意味着同时处理数字和它们的错误。(这是恐怖！)
• 数数所有10^10以下的斐波纳契数，并与它们进行比较。

到目前为止，最后一个变体是最简单的。