大 FIbonacci Java 时间超出

Question

我卡在了一个测试用例上。该问题需要在给定的时间段内计算一个大的斐波那契数。我已经通过了 10 个案例中的 8 个，并坚持了 9 个。

这是我的代码：

import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {




public static void main(String[] args) {
    Scanner sc  = new Scanner(System.in);
    BigInteger bi = sc.nextBigInteger();


    System.out.println(fib(bi));
}



public static BigInteger fib(BigInteger n) {
    BigInteger val=new BigInteger("10");
    int k = n.intValue();
    BigInteger ans = null;

    if(k == 0) {
        ans = new BigInteger("0");
    } else if(Math.abs(k) <= 2) {
        ans = new BigInteger("1");
    } else {
        BigInteger km1 = new BigInteger("1");
        BigInteger km2 = new BigInteger("1");

        for(int i = 3; i <= Math.abs(k); ++i) {
            ans = km1.add(km2);
            km2 = km1;
            km1 = ans;
        }
    }

    if(k<0 && k%2==0) { ans = ans.negate(); }
    return ans.mod(val);
}

}

提交后我得到以下超时结果。

我需要帮助来提高我的代码效率。

意见反馈：

Failed case #9/10: time limit exceeded Input: 613455

Your output:

stderr:

(Time used: 3.26/1.50, memory used: 379953152/536870912.)

请指导我。

您真诚的，维迪沙

Answer 1

我把评论中最容易实现的建议都采纳到了代码中

import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {


    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        BigInteger bi = sc.nextBigInteger();


        System.out.println(fib(bi));
    }


    public static BigInteger fib(BigInteger n) {
        int m = 10;
        BigInteger sixty = new BigInteger("60");
        int k = (n.mod(sixty)).intValue();
        int ans = 0;

        if(k == 0) {
            ans = 0;
        } else if(Math.abs(k) <= 2) {
            ans = 1;
        } else {
            int km1 = 1;
            int km2 = 1;

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = (km1 + km2)%m;
                km2 = km1;
                km1 = ans;
            }
        }

        if(k<0 && k%2==0) { ans = -ans; }
        return new BigInteger("" + ans);
    }

}

Answer 2

试试看：

public static int fibonacci(int n) {
    return (int)((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));
}

大 FIbonacci Java 时间超出

Large FIbonacci Java Time Exceeded

java

algorithm

fibonacci