问题描述: Fiboracci数列的地推公式为:Fn=F(n-1)+F(n-2),其中F1=F2=1;当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少?n的范围是1<=n<=1,000,000;
由于n非常大,如果把Fn的值算出来,数值非常大,变量不能保存很多位,所以,每求一次Fn的时候,都%10007,最后即可求出的Fn的余数,详细见代码;
- #include<stdio.h>
- int f(int n)
- {
- int f1,f2,f3;
- f1=1;
- f2=1;
- if(n<=2)
- return 1;
- else if(n>=3)
- {
- for(int i=3;i<=n;i++)
- {
- f3=(f1+f2)%10007;
- f1=f2;
- f2=f3;
- }
- return f3;
- }
- }
- int main()
- {
- int n;
- scanf("%d",&n);
- printf("%d",f(n));
- return 0;
- }
复制代码
|
|