单点时限: 2.0 sec
内存限制: 256 MB
有一个数列 {An},其中 A1=1,A2=2,An+2=An+1+An。
给你一个数字,问他是这个数列的第几项。
每行包括数列中的一项 Ak (k≤100000)。
总行数 T≤100。
输入格式
Something like:
2
3
5
8
13
输出格式
Something like:
2
3
4
5
6
提示
Java 和 Python 姿势好不会 MLE,想暴力有一点点难度。
正解当然是 C++ 啦,开动脑筋。
注意是 k≤100000,不是 ak≤100000
/*
思路:费波纳杰数列到100000已经很大了,故找一个合适的p,使其每一项可以模。
*/
#include
#include
#利用python自带的hash更容易解决
flag = [0,1,2]
for i in range(99998):
t = a + b
flag.append(hash(t))
a,b = b,t
while True:
try:
print(flag.index(hash(int(input()))))
except:
break