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;
}
}