Calculate the an % b where a, b and n are all 32bit integers.
Example
For 231 % 3 = 2
For 1001000 % 1000 = 0
Challenge
O(logn)
数学问题,要求O(log n)的时间复杂度,也就是每次去掉一半的计算量,先要找到对应的数学公式:
(a * b) % p = (a % p * b % p) % p
所以(a^n)%b = (a^n/2 * a^n/2 * a) % b = ((a^n/2 * a^n/2)%b * a%b) % b
注意int和long的转化,防止溢出。
class Solution { /* * @param a, b, n: 32bit integers * @return: An integer */ public int fastPower(int a, int b, int n) { // write your code here long ret = getPower(a, b, n); return (int)ret; } public long getPower(int a, int b, int n){ if(a == 0) return 0; if(n == 0) return 1 % b; if(n == 1) return a % b; long ret = getPower(a, b, n/2); ret *= ret; ret %= b; if(n % 2 == 1){ ret = ret * (a % b); } return ret % b; } };
Advertisements