1221: Fibonacci数列 [数学]
数学 数列 Fibonacci
2023-09-11 14:22:48 时间
1221: Fibonacci数列 [数学]
时间限制: 1 Sec 内存限制: 128 MB提交: 116 解决: 36 统计
题目描述
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
输入
输入包含一个整数n。
1 <= n <= 1,000,000
输出
输出一行,包含一个整数,表示Fn除以10007的余数。
样例输入
10
22
样例输出
55
7704
提示
在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。
来源
本来不想用数组来储存数列,只用一个递归的思想来解决问题,可是提交上去一直WA
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
void Fib(int x) { ans1 = ans2 = ans3 = 1; for(int i = 3; i <= x; i++) { ans3 = (ans1 + ans2)%10007; ans1 = ans2; ans2 = ans3; } }
后来看了看别人的代码,发现还是用了数组来储存数据,同时还用到了同余定理
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> int f[1000000+10]; int main() { int n; while(scanf("%d",&n)!=EOF) { f[1]=1; f[2]=1; for(int i=3;i<=n;i++) { f[i]=(f[i-1]+f[i-2])%10007; } printf("%d\n",f[n]); } return 0; }
同余定理
性质 4:若 a1≡b1(modm),a2≡b2(modm),….,an≡bn(modm),
则 a1+a2+…an≡b1+b2+…bn(modm)。 (性质 7 可以看成是性质 2
的一个延展。 )
相关文章
- 【BZOJ2671】Calc 数学
- 机器学习笔记之前馈神经网络(四)反向传播算法[数学推导过程]
- CodeForces 534C Polycarpus' Dice (数学)
- 《数学建模:基于R》一一1.3 非参数检验
- 【HDU 6036】Division Game (NTT+数学)
- 组合数学第一发 hdu 2451 Simple Addition Expression
- 2023美国大学生数学建模竞赛E题思路解析
- 2022年亚太杯数学建模竞赛(APMCM)ABC题思路资料汇总贴
- nyoj 70-阶乘因式分解(二)(数学)
- 【bzoj1925】[Sdoi2010]地精部落 组合数学+dp
- 1232: 买不到的数目 [DP、数学]