3423 - Fibonacci数列
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
Input
输入包含一个组数T,表示有T组测试数据。<span style="font-size:13.3333339691162px;line-height:1.5;"> (0<T<100)</span>
<br />
每组数据包含一个正整数N(0<N<1000)。
Output
对于每组数据，输出一行，包含一个整数，表示Fn除以10007的余数。
Examples
Input
2 10 22
Output
55 7704
Hint
中国剩余定理 (a+b)%M = (a%M + b%M)%M
Solution C
#include<stdio.h> int main() { long int a[1000],b,n,t; a[0]=1; a[1]=1; for(b=2;b<1000;b++) { a[b]=((a[b-2]+a[b-1])%10007); } scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%ld\n",a[n-1]); } }
Solution C++
#include<stdio.h> int main() { long long int a[1001]; const int MOD = 10007; int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); a[1] = 1; a[2] = 1; for(int i = 3;i <= n;i++) { a[i] = (a[i-1] + a[i - 2]) % MOD; } printf("%lld\n",a[n]); } return 0; }
Hint
中国剩余定理 (a+b)%M = (a%M + b%M)%M