Fibonacci数列

Fibonacci数列   时间限制：1.0s   内存限制：256.0MB 问题描述

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

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

输入格式 输入包含一个整数n。 输出格式 输出一行，包含一个整数，表示F n除以10007的余数。

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

样例输入 10 样例输出 55 样例输入 22 样例输出 7704 数据规模与约定 1 <= n <= 1,000,000。 import java.util.Scanner; public class Main { public static void main(String args[]){ int n = new Scanner(System.in).nextInt(); long sum=fun(n); long y=sum007; System.out.print(y); } public static long fun(int n){//计算F(n)的值 long f1=1; long f2=1; long a=0; if(n==1 || n==2){ a=1; }else if(n>=3) { for (int i=3; i <= n; i++){             a=f1+f2;             f1=f2;             f2=a;                      }} return a; }

}

下面为改进方法：

import java.util.Scanner; public class Main_1 {     public static void main(String[] args) {                  int f1 = 1;         int f2 = 1;         int n = new Scanner(System.in).nextInt();                          for (int i = 3; i <= n; i += 2){             f1 = (f1 + f2) % 10007;             f2 = (f1 + f2) % 10007;         }         if (0 != n % 2) {             System.out.println(f1);         }else {             System.out.println(f2);         }     } }