LintCode Q140 Fast Power in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2017年1月7日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
"""
@param a, b, n: 32bit integers
@return: An integer
"""
def fastPower(self, a, b, n):
# write your code here
# divide and conquer
# fast (a**n % b)
if n == 0:
return 1 % b
if n == 1:
return a % b
product = self.fastPower(a, b, n/2)
if n % 2 == 0:
ans = (product * product) % b
else:
ans = (product * product * a) % b
return ans
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。