刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

菲波那契数列（2024.3三级）

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数对10000取模的结果是多少。

时间限制：1000

内存限制：65536

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。

输出

n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对10000取模得到的结果。


样例输入

4
5
2
19
1

样例输出

5
1
181
1

使用微信搜索喵呜刷题，轻松应对考试！

答案：

对于每组输入，输出菲波那契数列中第a个数对10000取模的结果。

解析：

【喵呜刷题小喵解析】：

本题要求计算菲波那契数列中第a个数对10000取模的结果。

首先，我们需要理解菲波那契数列的定义：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

对于计算第a个菲波那契数，我们可以使用递归或者迭代的方法。但是，由于a的最大值为1000000，递归方法会超时，所以我们需要使用迭代方法。

迭代方法的思路如下：

1. 初始化前两个数为1。
2. 从第三个数开始，每个数都等于前两个数之和。
3. 在计算每个数的时候，都对10000取模，防止结果过大。

具体实现时，我们可以使用一个循环，循环a次，每次计算出一个菲波那契数，并对10000取模。最后输出这个模值即可。

需要注意的是，由于a的值可能很大，我们需要使用快速幂算法来优化计算过程，避免超时。快速幂算法的基本思路是将指数a拆分成二进制形式，然后利用菲波那契数列的性质，将计算过程优化为对数级别。

但是，本题的时间限制和内存限制都较小，所以我们可以直接使用迭代方法，不需要使用快速幂算法。

因此，我们可以按照上述思路编写代码，实现计算菲波那契数列中第a个数对10000取模的结果的功能。
创作类型：
原创

本文链接：菲波那契数列（2024.3三级） 菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share