PAT 斐波那契凤尾 (思维水题)

凤尾 (思维水题)"/>

PAT 斐波那契凤尾 (思维水题)

这还是一道蛮有意思的题

首先要知道, 斐波那契数列在大概95的时候就超出基本数据类型的最大存储long long的上限了

而如果直观的考虑用高精度也太麻烦了, 其实因为只需要输出后六位, 我们每次都只取后六位相加就好了, 也就是%1000000

这个地方记得要判断一下n多大时候才会超过6位, 然后用printf("%06d")输出后六位即可了

还有两个细节:

1. 斐波那契数列前两项应该是1, 1 但这题里面却是1 2

2.取后六位六位不是%100000, 而是%1000000, 也就是6个0

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1e5+5;int n, fib[maxn];
void init()
{fib[1] = 1, fib[2] = 2; //斐波那契第二项为2for(int i = 3; i <= maxn; i++)fib[i] = (fib[i-1]+fib[i-2])%1000000; //只取后6位
}int main()
{init();while(cin >> n){if(n <= 25)cout << fib[n] << endl;elseprintf("%06d\n",fib[n]); //输出后六位}return 0;
}