python - 由于运行时错误，一个测试用例失败

Question

我正在尝试欧拉计划problem 25在 HackerRank 上。

我尝试使用 Binet 的 Formula 进行强力方法.

import math

for _ in range(int(input())):
    numLen = int(input())
    for x in range(1, 5000):
        fib = 1/pow(5,.5)*(pow(((1+pow(5,.5))/2),x) - pow(((1-pow(5,.5))/2),x))
        if(numLen == len(str(int(fib)))):
            print(x)
            break

这里 5000 是一个任意数字，基于假设输入不超过这个数字，问题不在这里，因为它是一个运行时错误，我认为这是因为它超出了整数范围(不确定)。

它还能在不到 0.25 秒的时间内计算出其他测试用例。

我做了一些搜索，发现 this .

但是通过递归方法:

import math

for _ in range(int(input())):
    a = 1
    b = 0
    n = int(input())
    term = 1
    while len(str(a)) != n:
        a, b = a+b, a
        term+=1
    print (term) 

超过 10 秒时超时。

您能帮我想办法改进第一种方法并优化第二种方法吗？

注意:我尝试将 pow() 值存储在变量中而不是重新计算，但没有太大帮助。

Answer 1

只需在示例中使用第二种方法，而不是为输入中的每一行单独计算值，计算值 1...5000 一次并缓存它们:

res = [0]
a = 0
b = 1
term = 1

while len(res) <= 5000:
    a, b = b, a + b
    if len(str(a)) >= len(res):
        res.append(term)
    term += 1

print('\n'.join(str(res[int(input())]) for _ in range(int(input()))))

对于输入2 3 4，它将产生预期的输出12 17。在我的机器上预计算这些值大约需要 3 秒。