1571: Fibonacci数列

1571: Fibonacci数列

时间限制: 1 Sec   内存限制: 128 MB

题目描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入

包含一个整数n

输出

一行，包含一个整数，表示Fn除以10007的余数。

样例输入 Copy

10

样例输出 Copy

55

提示

数据规模与约定
1 <= n <= 1,000,000。

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;

cin>>n;

int mo=10007;

int a=1,b=1;

for(int i=3;i<=n;i++){

int c=a+b;

a=b%mo;b=c%mo;

}

cout<<b<<endl;

return 0;

}