入门训练 Fibonacci数列

描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入

输入描述:
输入包含一个整数n。
输入样例:
10

输出

输出描述:
输出一行，包含一个整数，表示Fn除以10007的余数。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

输出样例:
55

输入样例 1 

参考上文 

输出样例 1

参考上文

提示

HINT:时间限制：1.0s 内存限制：256.0MB
1 <= n <= 1,000,000。

来源

蓝桥杯练习系统 ID: 4 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T4

思路：

        如果计算出fn的值再去求余数就会超时，但是再求fn的过程中进行求余数可以降低复杂程度，两数相加的余数==一个数的余数加上另一个数的余数。

import java.util.Scanner;

public class old1005 {
    public static void main(String[] args) {
        int i;
        Scanner input = new Scanner(System.in);
        i = input.nextInt();
        int f1 = 1, f2 = 1, f3 = 0;
        if (i == 1 || i == 2) {
            System.out.println(1);
        } else {
            for (int j = 2; j < i; j++) {
                f3 = (f1 + f2) % 10007;
                f1 = f2;
                f2 = f3;
            }
            System.out.println(f3);
        }
    }
}