问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
**说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
**
只通过部分用例：
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a = 1;
int b = 1;
int c = 0;
if(n == 1||n==2)
c = 1;
else
for(int i = 3;i<=n;i++) {
c = a + b;
a = b;
b = c;
}
System.out.println(c%10007);
}
}
可以通过全部用例：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a = 1;
int b = 1;
int c = 0;
if(n == 1||n == 2)
c = 1;
else
for(int i = 3;i<=n;i++) {
c = (a + b)%10007;
a = b%10007;
b = c%10007;
}
System.out.println(c);
}
}
在遇到本题后首先是想用递归先求出第n个斐波那契数，再对10007取余，但提交后显示运行超时。于是我想到可能是因为递归耗时过多，便采用了非递归，提交后只有部分测试用例通过。之后又仔细看了题目和说明，便直接在求斐波那契数列的过程中求出了该斐波那契数对10007取余的结果，提交后通过全部测试用例。
之后在网上查找看了很多资料，但还是不太明白直接在过程中求余数和先算出斐波那契数在求余有什么区别，麻烦有知道的人解答一下，谢谢！
因为在中间运算的过程中，比如说 a + b 算出来的数超过 int 的范围的话，会导致存入 c 中的数出现错误，从而导致接下来的计算出现错误，所以需要在每一步都给他 % 上 10007，这样才能保证数不会出现错误。（斐波那契在后面的增长速度非常快）
tips ： 在每一步都 % 上 10007，这样所以运算的数都在0 ~ 10007 ，只会在这个数范围内进行相加减，不会爆范围问题。相当于只进行斐波那契数中的所有数在 0 ~ 10007 范围内的运算，可以自己写几个数试试。