lintcode-fast-power

发表于   |   分类于 ，   |  

题目大意

　　http://www.lintcode.com/zh-cn/problem/fast-power

　　快速幂运算

题目分析

　　快速幂，将n转化成二进制逐位累乘

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
        }
        long tmp = a;
        long ans = 1;
        while (n > 0) {
            if ((n & 1) != 0) {
                ans = (ans * tmp) % b;
            }
            tmp = (tmp * tmp) % b;
            n >>= 1;
        }
        return (int)ans;
    }
}