关于模运算的行为？

Question

我用python为下面的codechef问题http://www.codechef.com/problems/MOVES/编写了以下程序

import sys

tokenizedInput = sys.stdin.read().split()
mod=1000000007
arr=[1]*5001
for i in range(1,5001):
    arr[i]=(arr[i-1]*i)%mod

def combo(r,n,mod):
    q=arr[n]
    print q
    r=(arr[r]*arr[n-r])
    print r
    return ((q/r)%mod)

elm=0

for i in range (0,5001):
    n=int(tokenizedInput[elm])
    elm=elm+1
    k=int(tokenizedInput[elm])
    elm=elm+1
    if(n==0 and k==0):
        break
    out=0
    if(((k-1)/2)!=(k/2)):
      out=(2*combo((k-1)/2,n-2,mod)*combo(k/2,n-2,mod))%mod
    else:
      out=(2*combo(k/2,n-2,mod)**2)%mod
    print out

但是我的模函数不能正常工作，比如n=498 而r=2 combo（）返回的答案是0，因为q=243293343，r=1428355228 如何在arr[]中执行模运算来纠正这个错误？在

Answer 1

我的问题得到了优化的答案，但我鼓励自己的解决方案 错误是

return ((q/r)%mod)

mod为1000000007即质数是错误的，它必须写成

r=(arr[r]*arr[n-r])%mod

return (q*Power(r,mod-2))%mod

幂函数在哪里

^{1}$

但如果有人解释使用return（base*Power（base，expo-1）%mod）背后的数学原理，那将是非常有帮助的

Answer 2

当我们除法（a/b）%MOD时，我们会这样做。在

（a/b）%模式

（a*逆（b））%MOD//必须求b的逆。要求b的逆，请使用Fermat定理。在

注意不要先除以a/b然后取MOD，先求b的逆，然后做a*b，然后再进行MOD。在

Answer 3

上面的幂函数通过使用所谓的平方求幂来计算O（log（b））中的a^b。想法很简单：

^{1}$

这个想法可以很容易地实现，如下所示：

^{pr2}$

上面的幂函数只是一种递归的方法。 就像你问的那样

but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)

这与检查expo是否奇数相同，然后将base与base^（expo-1）相乘，这样新的expo即（expo-1）将变为偶数并且可以进行重复的平方

更多信息请参考：

Topcoder Tutorial

wiki: expo by squaring