pow (a, nCr) % m을 효율적으로 계산 함

Question

pow (a, nCr) % b를 계산하는 프로세스가 있다고 생각합니까? 하지만 프로그래밍에서이 문제를 어떻게 효율적으로 해결할 수 있는지 알고 싶습니다.

Answer 1

나는 단지 ~O(n^2*log(m)) 인 방법을 생각할 수 있으며 큰 정수를 사용할 필요가 없습니다. 나는 을 감안할 수 있고 어떤 k에 대해 totient (m/gcd(a^k,m))을 감안할 수 있다면 좀 더 빠른 (O(k*log(m)*log(n))과 같은) 접근법을 사용합니다.하지만 꽤 털이 있습니다. O(n^2*log(m)) 접근 어쨌든

, 우리는 사실을 활용할 것이다 것을의 nCr == (N-1) C (R-1) + 여기서 연산의

(N-1) CR 활용의 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)