擅长:python、mysql、java
<p>上面的幂函数通过使用所谓的平方求幂来计算O(log(b))中的a^b。想法很简单:</p>
^{1}$
<p>这个想法可以很容易地实现,如下所示:</p>
^{pr2}$
<p>上面的幂函数只是一种递归的方法。
就像你问的那样</p>
<blockquote>
<p>but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)</p>
</blockquote>
<p>这与检查expo是否奇数相同,然后将base与base^(expo-1)相乘,这样新的expo即(expo-1)将变为偶数并且可以进行重复的平方</p>
<p>更多信息请参考:</p>
<p><a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting" rel="nofollow">Topcoder Tutorial</a></p>
<p><a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow">wiki: expo by squaring</a></p>