题目描述
在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。
给定整数n,求Fibnmod10000。
算法1 神秘水法
算法分析
由于斐波那契数列是二阶递推数列, 根据抽屉原理
若有两个连续两项模10000相同
则以后的所有数模10000均会相同
于是我们可知模任意一个数的斐波那契数列从某一项开始就会开启循环,
庆幸地是模10000时从第一项就开始了循环且周期不大。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=15000;
const ll MOD=10000;
ll n,m ,t,x,y;
ll f[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
f[1]=1;f[2]=1;
for(int i=3;i<=MAXN;++i)f[i]=(f[i-1]+f[i-2])%MOD;
while(cin>>x&&x!=-1)
{
x=x%MAXN;
cout<<f[x]<<endl;
}
return 0;
}
萌新想问下为啥是15000一个循环啊
这个是我试出来的,而且因为我太菜,不知道具体为什么15000一个循环,对您这么久的等待等出这个答复感到非常非常的抱歉
哇nbnbnbnbnbnb
这个解法很棒啊
感谢大佬