Python中的模冪運算

我試圖用Python 2.7.9作爲我的編程語言來解決SPOJ中的ZSUM問題，並設計了一個程序來做到這一點。由於代碼運行完美，但在裁判給予TLE，我想它不夠快。是否有可能優化下面的代碼來滿足裁判的要求，或者使用Python無法擊敗挑戰。Python中的模冪運算

鏈接的問題：http://www.spoj.com/problems/ZSUM/

def zsum(n,k): 
    a=2*pow(n-1,k,10000007) 
    b=pow(n,k,10000007) 
    c=2*pow(n-1,n-1,10000007) 
    d=pow(n,n,10000007) 
    zsum=(a+b+c+d)%10000007 
    print zsum 

def main(): 
    while True: 
    n,k=map(int,raw_input().split()) 
    if n==k==0: 
     break 
    else: 
     zsum(n,k) 
main()

來源

2015-06-11 Akash Singh

http://en.wikipedia.org/wiki/Modular_exponentiation –

@AndrewJaffe我之前讀過這篇文章，並且在上面的代碼中使用了Python的內置模冪運算，但它仍然不夠快。 –

由於在2335個成功提交中共有零個可接受的python解決方案，我認爲，無論您對解決方案進行了多少優化，它都不太可能被python接受。雖然python是一種非常有用的語言，但它在編程競賽中並不是首選，因爲它非常慢（與C/C++相比）。如果你知道如何用C++編寫代碼，你一定要試一試，儘管你必須寫你自己的模冪運算程序。

來源

2015-06-11 17:49:46

我不知道這是否會幫助（如果你看過這個問題的評論，你會看到有人說，這是不可能在Python來解決 - 這可能發生與較慢的語言在線法官），但你可以優化代碼：

def zsum(n,k): 
    a=2*pow(n-1,k,10000007) # (1) 
    b=pow(n,k,10000007)  # (2) 
    c=2*pow(n-1,n-1,10000007) # (1) 
    d=pow(n,n,10000007)  # (2) 
    zsum=(a+b+c+d)%10000007 
    print zsum

注意，在(1)，你是計算pow(n - 1, min(k, n - 1))兩次。您可以計算一次，然後僅使用模冪運算剩餘的。相同的(2)。

來源

2015-06-11 17:05:01 IVlad

感謝您的優化，但仍然不夠快。 –

Python中的模冪運算

回答

相關問題