java - 斐波那契 n 模 m

Question

我正在尝试计算 𝐹𝑛 模 𝑚，其中 𝑛 可能非常大:高达 10^18，𝐹𝑛 是第 n 个斐波那契数这是我的代码，它适用于小数字，但对于大数字，它会抛出 OutOfMemoryError 或 NegativeArraySizeException。

import java.util.*;

public class FibonacciHuge {
private static long getFibonacciHugeFast(long n, long m) {
long[] arr = new long[(int) n + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n + 1; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % m;
}
return arr[(int) n];
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
System.out.println(getFibonacciHugeFast(n, m));
}
}

Answer 1

这是对您的两个异常/错误的解释。

1. OutOfMemoryError 异常:由于您正在尝试创建一个巨大的数组，远远超过了可能的大小。引用这个问题Do Java arrays have a maximum size?
2. NegativeArraySizeException:由于您将 long 转换为整数(代码 long[] arr = new long[(int) n + 1];)。读这个:Primitive data types . (基本上你在某个时候溢出，结果整数是负数)