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"stdio.h" int f(int n) { int x1=1; int x2=1; int sum=0; if(n==1||n==2) return 1; int i; for(i=3;i<=n;i++) { sum=x1+x2; if(sum>10007) sum%=10007; x1=x2; x2=sum; } return sum; } int main() { int n; scanf("%d",&n); printf("%d\n",f(n)); return 0; } View Code