Fast Power

Java

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        long ans = 1 % b, tmp = a;
        while(n > 0) {
            if (n % 2 == 1) {
                ans = ans * tmp % b;
            }
            tmp = tmp * tmp % b;
            n = n / 2;
        }
        return (int)ans;
    }
}

Python

class Solution:
    """
    @param a: A 32bit integer
    @param b: A 32bit integer
    @param n: A 32bit integer
    @return: An integer
    """
    def fastPower(self, a, b, n):
        # write your code here
        if n == 0:
            return 1 % b
        if n % 2 == 0:
            tmp = self.fastPower(a, b, n / 2)
            return tmp * tmp % b
        else:
            tmp = self.fastPower(a, b, n / 2)
            return tmp * tmp * a % b