java - 给定斐波那契数列中的数字总和

Question

我的任务是确定从 A 到 B 的斐波那契数列中的数字之和是否可以被数 D 整除。

我使用快速加倍算法在数列中找到所需的数，并使用公式：
F _a + .. . + F _b = F _b+2 - 1 - (F _a+1 - 1) - 确定级数之和，但这还不够。为了测试，我取了一个从 A = 10,000,000 到 B = 20,000,000 的序列，数字 D = 987654，程序在 3.3 秒内执行，这已经很多了。有没有办法优化我的代码？

class Solution {

    private static Map<BigDecimal, BigDecimal> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<>();
        previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
        previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
    }

    private static BigInteger totalSum;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int nb = in.nextInt();

        for (int i = 0; i < nb; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int d = in.nextInt();

            totalSum = calculateTotalSum(a, b);
            System.out.println(checkSum(totalSum, a, b, d));
        }
    }

    private static BigInteger calculateTotalSum(int start, int finish) {
        BigInteger res1 = fibDoubleFast(finish + 2).subtract(BigInteger.valueOf(1));
        BigInteger res2 = fibDoubleFast(start + 1).subtract(BigInteger.valueOf(1));

        return res1.subtract(res2);
    }

    private static String checkSum(BigInteger sum, int start, int finish, int d) {
        BigInteger result = sum.remainder(BigInteger.valueOf(d));

        return result.longValue() > 0
                ? String.format("F_%s + ... + F_%s is NOT divisible by %s", start, finish, d)
                : String.format("F_%s + ... + F_%s is divisible by %s", start, finish, d);
    }

    private static BigInteger fibDoubleFast(int n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int m = 0;
        for (int bit = Integer.highestOneBit(n); bit != 0; bit >>>= 1) {
            BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));
            BigInteger e = multiply(a, a).add(multiply(b, b));
            a = d;
            b = e;
            m *= 2;

            if ((n & bit) != 0) {
                BigInteger c = a.add(b);
                a = b;
                b = c;
                m++;
            }
        }
        return a;
    }

    private static BigInteger multiply(BigInteger x, BigInteger y) {
        return x.multiply(y);
    }
}

标签： javaperformanceoptimizationfibonacci

Answer 1

对于较小的 D 值（我认为小于 2^31），您可以使用 long 完成整个代码，并对每个中间结果执行 mod D。

private static long fibDoubleFastModD(int n, long m) {
        ...
        long d = (...) % m;
        long e = (...) % m;
        ...  
}