Fast Power

Fast Power (leetcodelintcode)

Description
Calculate the a^n % b where a, b and n are all 32bit integers.

Example
For 231 % 3 = 2
For 1001000 % 1000 = 0

Challenge 
O(logn)

解题思路

本题目主要考察快速幂的实现，以及 int 类型数据溢出的处理。

快速幂实现的思路是a ^ n = (a ^ n/2) * (a ^ n/2)，这里需要注意的是当n为奇数时需要再多乘一个a。在具体实现时，对于n == 0和n == 1这两种情况也需要单独处理。

题目中提到a和b都是32位整数，所以在计算过程中中间变量使用long类型存储以免溢出。另，在本题中假定a和b都是正数。

本题目还用到了整数取模操作的以下特点：(a * b) % p =((a % p) * (b % p)) % p。

算法复杂度

• 时间复杂度： O(logn) 。

易错点

1. 注意对 int 类型数据溢出的处理。

Java 实现

class
Solution
{

/*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
public
int
fastPower
(
int
 a, 
int
 b, 
int
 n)
{

if
 (n == 
1
) {

return
 a % b;
        }

if
 (n == 
0
) {

return
1
 % b;
        }


long
 product = fastPower(a, b, n / 
2
);
        product = (product * product) % b;

if
 (n % 
2
 == 
1
) {
            product = (product * a) % b;
        }


return
 (
int
) product;
    }

};

参考

1. Lintcode: Fast Power 解题报告 | Yu's garden