入门训练 Fibonacci数列

入门训练 Fibonacci数列 

问题描述

Fibonacci数列的递推公式为：F_n=F_n-1+F_n-2，其中F₁=F₂=1。

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

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

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

样例输入 10 样例输出 55 样例输入 22 样例输出 7704 数据规模与约定 1 <= n <= 1,000,000。

#include<iostream> using namespace std; int main () {     int n;     cin>>n;     int sum;     int n2=1,n1=1;  //a为f（n-2），b为f（n-1）     if(n==1|n==2)     {         sum=1;     }     else     {         for(int i=3; i<=n; i++)         {             sum=(n2+n1)007;             n2=n1;             n1=sum;         }     }             cout<<sum<<endl;     return 0; }