快速幂算法

快速幂公式：

$$a^{b}modc$$

推导在这里：推导过程

int PowerMod(int a, int b, int c) { int ans = 1; a = a % c; while(b > 0) { if((b & 1) == 1) // 这里注意 & 的优先级比 == 小，需要括号 ans = (ans * a) % c; b >>= 1; a = (a * a) % c; } return ans; }

这里可以热身一下：

class Solution { public double myPow(double x, int n) { double res = 1; long b = n; // 这里int会越界，所以要用long while(b > 0){ if((b & 1) == 1) res *= x; b >>= 1; x *= x; } if(b < 0) b *= -1; while(b > 0){ if((b & 1) == 1) res /= x; b >>= 1; x *= x; } return res; } }