フィボナッチシリーズの部分和の最後の桁を見つけようとしています

Question

#python2 
def sum_fib(m,n): 
    a=list() 
    a.append(0) 
    a.append(1) 
    i=2 
    while i<=n: 
     a.append((a[i-1]+a[i-2])%10) 
     if a[i]==1 and a[i-1]==0: 
      break 
     i+=1 
    if n>60: 
     a.pop() 
    #res=sum(a)%10 
    q=n-m 
    j=m%60 
    su=0 

    while q>=0: 
     su+=a[j] 
     j+=1 
     if j==60: 
      j=0 
     q-=1 

    return su%10 


if __name__=='__main__': 
    num=[int(x) for x in raw_input().split()] 
    print sum_fib(num[0],num[1]) 

このコードは正常ですが、大きなフィボナッチ数には時間がかかります。これで私を助けてください。 1 100000000 がtime limit exceeded-> error Time used: 9.36/5.00

Answer 1

あなたはFibonacci 60 Repeating Patternを使用しようとしているではなく、効率的に取得：入力の場合

次のループでは、あなたはまだ潜在的にフィボナッチ数の数千人を集めると、あなただけの60を必要としながら、これらの60個の数字を何度も実行する必要がないようにするには、最後のdigi 60個のフィボナッチ数の合計のうち、tは常に0です。これは実際には、最初の60個のフィボナッチ数の一部だけを数千に加算する必要はないことを意味します。 。

を入力変数として60をモジュロとして取り込み、必要な合計を計算するために60個のフィボナッチのリストを実行します。ここで

は適応コードです：

def sum_fib(m,n): 
    if m > n: 
     return 

    # Collect 60 Fibonnaci numbers 
    a = [0, 1] 
    for i in xrange(2, 60): 
     a.append(a[i-1] + a[i-2]) 

    # Simplify the input arguments, as the last digit pattern repeats with a period of 60, 
    # and the sum of 60 such consecutive numbers is 0 mod 10: 
    m = m % 60 
    n = n % 60 
    # Make sure n is greater than m 
    if n < m: 
     n += 60 

    su = 0 
    for j in xrange(m, n+1): # Assume n index is inclusive 
     su += a[j % 60] 

    return su % 10 

は、それがrepl.it