lintcode: Fast Power

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

Example For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge O(logn)

思路参见我的博客 ​​幂模运算​​

class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        // write your code here
        long long res=1;//用int的话中间会溢出
        long long base=a;

        if(n==0){
            return 1%b;
        }

        while(n){
            int bi=n%2;
            n/=2;
            if(bi){
                res=(res*base)%b;
            }
            base=(base*base)%b;
        }

        return res;
    }
};