140. Fast Power

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

public class Solution {
    /**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        // base case
        if(n == 0){
            return 1 % b;
        }
        
        if(n == 1){
            return a % b;
        }
        
        
        long ret = 0;
        // (a * b) % p = (a % p * b % p) % p
        ret = fastPower(a, b, n/2);
        ret *= ret;
        ret %= b;
        
        if(n % 2 == 1){
            ret *= a % b;
        }
        
        return (int) (ret % b);
    }
}