[LintCode] Fast Power

Problem

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

Example

For 2^31 % 3 = 2

For 100^1000 % 1000 = 0

Challenge

O(logN)

Note

应用求余公式: (a * b) % p = (a % p * b % p) % p
使用分治法，不断分解a^n为a^(n/2)，最终的子问题就是求解a^1或者a^0的余数。
唯一要注意的就是，若n为奇数，要将余数和a再代入求余公式，运算一次。

Solution

class Solution {public int fastPower(int a, int b, int n) {if (n == 0) return 1 % b;if (n == 1) return a % b;long product = fastPower(a, b, n/2);product = product * product % b;if (n % 2 == 1) product = product * a % b;return (int) product;} }

总结

以上是生活随笔为你收集整理的[LintCode] Fast Power的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。