Fast Power

Source

• lintcode: Fast Power

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)

题解

数学题，考察整数求模的一些特性，不知道这个特性的话此题一时半会解不出来，本题中利用的关键特性为：

(a * b) % p = ((a % p) * (b % p)) % p

即 a 与 b 的乘积模 p 的值等于 a, b 分别模 p 相乘后再模 p 的值，只能帮你到这儿了，不看以下的答案先想想知道此关系后如何解这道题。

首先不太可能先把 $a^n$ 具体值求出来，太大了... 所以利用以上求模公式，可以改写 $a^n$ 为：

$a^n = a^{n/2} \cdot a^{n/2} = a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot = ...$

至此递归模型建立。

Python

class Solution:
    """
    @param a, b, n: 32bit integers
    @return: An integer
    """
    def fastPower(self, a, b, n):
        # write your code here
        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%b)*(product%b))%b
        if n%2==1:
            product =  ((product%b)*(a%b))%b
        return product

Java

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if(n==0) return 1%b;
        if(n==1) return a%b;
        if(n<0){
            a=1/a;
            n=-n;
        }
        //use long to prevent overflow
        long product = fastPower(a, b, n/2);
        product = ((product%b)*(product%b))%b;
        if(n%2==1){
            product = ((product%b)*(a%b))%b;
        }
        return (int)product;
    }
};