# -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 50: Pow(x, n)https://leetcode.com/problems/powx-n/ Implement pow(x, n). === Comments by Dabay===技巧在于用x的平方来让n减半.同时注意n为负数的情况,以及n为奇数的情况.''' class Solution: # @param x, a float # @param n, a in
快速幂 问题描述: 计算a ** n % b 其中a.b和n都是32位的非负整数 即求a的n次方对b的余数 问题示例: 例如:2**31%3=2 --- 代码实现如下 class Solution: def fastPower(self, a, b, n): ans = 1 while n > 0: if n % 2 == 1: ans = ans * a % b a = a * a % b n = n / 2 return ans % b if __name__ == '__main__':