Power Mod

Calculates a to the power of b, mod c.

(x*y)%z == ((x%z)*y)%z == (x*(y%z))%z

Examples:

PowMod(2,3,5) = 2*2*2 % 5 = 8%5 =3

PowMod(3, 6, 7) = 3*3*3*3*3*3 % 7 = 729%7 =1.

PowMod(16,16,5) = 1

Solution: recursion O(logb)

public int powmod(int a , int b , int c){
    return pow(a, b) % c;               
}  
// double a
private int pow(int a, int b) {
    if (b == 0)        return 1;
    if (b % 2 == 0)        return pow(a * a, b / 2);
    else    return a * pow(a * a, b / 2);
}

Pow(x, n)

    public double myPow(double x, int n) {
        double res = 1;
        long N = Math.abs((long) n); //关键一步
        while (N > 0) {
            if ((N & 1) == 1) {
                res *= x;
            }
            x *= x;
            N >>= 1;
        }
        return n < 0 ? 1 / res : res;
    }