原題
計(jì)算a^n % b，其中a，b和n都是32位的整數(shù)报腔。
例如 2^31 % 3 = 2
例如 100^1000 % 1000 = 0
解題思路
- 本題主要利用了整數(shù)求模的一些特性
(a * b) % p = ((a % p) * (b % p)) % p
- 所以求解n次方可以轉(zhuǎn)化為n/2次方....
- 典型divide & conquer
- 需要注意對(duì)n=0, n=1, n<0情況的分析
完整代碼
class Solution:
"""
@param a, b, n: 32bit integers
@return: An integer
"""
def fastPower(self, a, b, n):
if n == 1:
return a % b
elif n == 0:
return 1 % b
elif n < 0:
return -1
product = self.fastPower(a, b, n / 2)
product = (product * product) % b
if n % 2 == 1:
product = (product * a) % b
return product
