【蓝桥杯】BEGIN-4 Fibonacci数列

• 2019 年 11 月 8 日
• 笔记

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/86562090

题目描述：

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

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

输入格式：

输入包含一个整数n（1 <= n <= 1,000,000）。

输出格式：

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

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

输入样例1：

10

输出样例1：

55

输入样例：

22

输出样例：

7704

解题思路：

这TM不就是一道无脑递归的水题吗？诶？！提交之后居然TLE 对不起 是我小瞧这道题了。没那么简单~ 既然不能无脑递归，就老老实实地按照题目意思来吧。

AC代码：TLE代码：

#include <bits/stdc++.h>  using namespace std;    int Fib(int n)  {      if(n == 1 || n == 2)      {          return 1;      }      return Fib(n-1)+Fib(n-2);  }    int main()  {      int n;      scanf("%d",&n);      printf("%dn",Fib(n)%10007);      return 0;  }

AC代码：

#include <bits/stdc++.h>  using namespace std;    int Fib(int n)  {      //a作为f(n),b作为f(n+1)      int a = 1, b = 1;      for (int i = 1; i < n; i++)      {          swap(a,b);  //更新f(n)          b = (a+b)%10007;  //更新f(n+1)      }      return a;  }    int main()  {      int n;      scanf("%d",&n);      printf("%dn",Fib(n));      return 0;  }