実行時エラーにより1つのテストケースが失敗する

Question

HackerRankでProject Euler problem 25を試していました。

私はBinet's 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が見つかりました。

が、その再発法で：それは10秒を超えるよう

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) 

はタイムアウトを提供します。

第1の方法を改善し、第2の方法を最適化する方法を見つけることができますか？

注：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秒かかります。

Answer 2

pow(x, y)は、常にx**yより遅く、また、pow()の方法は、長い整数には使用できません。

x**yを試してみて、それが少し速くなり