一道蓝桥杯斐波那契数列题 数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

Question

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

public void solve2(int a){
int [] arr=new int[a+1];
arr[1]=arr[2]=1;
for(int i=3;i<arr.length;i++){
arr[i]=(arr[i-1]+arr[i-2])%10007;//对每一个斐波那契数列进行取余数
}
System.out.println(arr[a]);
}
我想问一下 arr[i]=(arr[i-1]+arr[i-2])%10007 对每一斐波那契数列进行取余是什么意思 如何理解
我是这样理解的 例如 当i=4时 余数为 i=3的余数加i=2的余数 再除以10007取余 这样对吗 为什么等于先求值再取余

Answer 1

什么是求余？就是求无法除尽的部分，你可以试一下，有两个数m、n,且m>n,那么会有n%m =n.也就是说在Fn小于10007之前，其实是否%10007并没有价值，而关键就在后面超出10007的部分，当你的Fn超过10007时，每次循环中的%10007你可以理解为-10007，这样就可以将Fn限定在一个范围中，不会太大，导致耗时太长。而再关键的地方就是为什么在Fn超出10007之后会依旧成立，其实很简单，因为这是一个加法，你就算算到无穷大的Fn也还是由n*Fn+余数部分，所以这个直接求余才能成立。