【两次过】Lintcode 140. 快速幂

计算an % b，其中a，b和n都是32位的非负整数。

样例

例如 231 % 3 = 2

例如 1001000 % 1000 = 0

挑战

O(logn)

解题思路：

肯定不能直接算，要溢出。注意这里有个公式：

(c*d)%b={(c%b) * (d%b)} % b

每次对n／2，减少一半的计算量。若n为偶数，则上式中c=d=a^(n/2)，若n为奇数，则c=a^(n/2)，d=a^(1+(n/2))，直至n=0或n=1;每次返回余数，平方再求余。注意n是奇数偶数，如果是奇数，要补回舍去的1次幂，即乘以a％b，再求余。

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
        if(n == 0)
            return 1%b;
        if(n == 1)
            return a%b;
        
        long remainder = (long)fastPower(a,b,n/2);
        remainder = remainder * remainder % b;
        
        if(n%2 == 1)
            remainder = remainder * (a%b) % b;
            
        return (int)remainder;
    }
}