有效計算pow（a，nCr）％m

Question

我認爲有一些計算pow（a，nCr）％b的過程。 但是我想知道如何在編程中有效地解決這個問題？

Answer 1

我能想到的方法只有~O(n^2*log(m))，並不需要使用大整數。如果你的因子可以是因子m，並且你可以將因子totient（m/gcd(a^k,m)）設置爲k，我有一個更快的概念（如O(k*log(m)*log(n))），但它會變得非常多毛。

在任何情況下爲O(n^2*log(m))的做法，我們將利用這一事實nCr的==（N-1），C（R-1）+（N-1）鉻

這裏的計算nCr的其中利用了：

def nCr(n0,r0): 
    memoized = {} 

    def go(n,r): 
    if r == 0 or r == n: 
     return 1 
    if (n,r) not in memoized: 
     memoized[(n,r)] = go(n-1,r-1) + go(n-1,r) 
    return memoized[(n,r)] 

    return go(n0,r0) 

您powChooseMod函數的代碼是幾乎相同：

def powChooseMod(a,n0,r0,m): 
    memoized = {} 

    def go(n,r): 
    if r == 0 or r == n: 
     return a 
    if (n,r) not in memoized: 
     memoized[(n,r)] = go(n-1,r-1) * go(n-1,r) % m 
    return memoized[(n,r)] 

    return go(n0,r0)