140. fast power

public class  {
    
     * @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
        /*
        (a+b) % p = (a%p + b%p) % p
        (a-b) % p = (a%p - b%p) % p
        (a*b) % p = (a%p * b%p) % p
        (a^b) %p = ((a%p) ^ b) %p
        */
        if (n < 0) {
            n = -n;
            a = 1 / a;
        }
        if (n == 1) {
            return a % b;
        }

        if (n == 0) { // 一定要考虑n=0
            return 1 % b;
        }
        long temp = fastPower(a, b, n/2); //!!!这里一定是long；
        temp = (temp * temp) % b; //一定先这一步，否则溢出；
        if (n % 2 == 1) {
            return (int) ((temp * (a % b)) % b);
        } else {
            return (int) temp;
        }



    }
}