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

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取余 这样对吗 为什么等于先求值再取余

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

(a + b) % p = (a % p + b % p) % p

Fn除以10007的余数 就是取模%

import java.util.Scanner;

public class Main2 {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a = fn(n);
    System.out.println(a);
}

private static int fn(int n) {
    if (n==1||n==2) {
        return 1;
    } else {
        return (fn(n-1)+fn(n-2))%10007;
    }
}

}

http://blog.csdn.net/u012110719/article/details/41704381

x%10007就是x / 10007，整除后剩下的值。
x%10007 + x整除10007*10007=x

Fn = n*10007+余数部分