Fast Power

题目：

Calculate the an % b where a, b and n are all 32bit integers.

分析：

标准的divide and conquer但是需要考虑n为奇数或者偶数的问题

解法：

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