Fast Power 140

Question

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

Example

For 2^31 % 3 = 2

For 100^1000 % 1000 = 0

Challenge

O(logn)

Solution

首先%的公式为(a b) % p = (a % p b % p) % p

因此这道题可以将a^n拆分：

当n为奇数时:

a^n % b

＝(a^(n/2) a^(n/2) a) % b

= ((a^(n/2) a^(n/2)) % b a % b) % b

当n为偶数时:

a^n % b

＝(a^(n/2) * a^(n/2)) % b

代码如下：

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        //corner case
        if(b == 0 || n < 0){
            return -1;
        }

        if(b == 1){
            return 0;
        }

        if(n == 0 || a == 1){
            return 1 % b;
        }

        if(n == 1){
            return a % b;
        }
        //a^(1/2) % b
        long product = fastPower(a, b, n / 2);
        //((a^(1/2) % b) * (a^(1/2) % b)) % b
        product = (product * product) % b;
        //当n为奇数时，还要再乘以一个a
        if(n % 2 == 1){
            //(product % b * a % b) % b = (product * a) % b
            product = (product * a) % b;
        }

        return (int) product;
    }
};