【兩次過】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;
    }
}