Fast Power

问题：Calculate the $a^n$% b where a, b and n are all 32bit integers.

Example from Lint

Math problem, have to know the equivalences of modulo %

1. (a+b) mod n =( (a mod n) +(b mod n) ) mod n
2. ab mod n = ((a mod n) (b mod n)) mod n
3. (a mod n) mod m = a mod n

public int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        } else if (n == 0) {
            return 1 % b;
        } else if (n < 0) {
            return -1;
        }

        // (a * b) % p = ((a % p) * (b % p)) % p
        // use long to prevent overflow
        long product = fastPower(a, b, n / 2);
        product = (product * product) % b;
        if (n % 2 == 1) {
            product = (product * a) % b;
        }

        // cast long to int
        return (int) product;
    }