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的转化，防止溢出。
比较严谨的做法：
1 class Solution { 2 /* 3 * @param a, b, n: 32bit integers 4 * @return: An integer 5 */ 6 public int fastPower(int a, int b, int n) { 7 // write your code here 8 long ret = getPower(a, b, n); 9 return (int)ret; 10 } 11 public long getPower(int a, int b, int n){ 12 if(a == 0) return 0; 13 if(n == 0) return 1 % b; 14 if(n == 1) return a % b; 15 16 long ret = getPower(a, b, n/2); 17 ret *= ret; 18 ret %= b; 19 if(n % 2 == 1){ 20 ret = ret * (a % b); 21 } 22 return ret % b; 23 } 24 };
我当时的做法：
1 class Solution { 2 public int fastPower(int a, int b, int n) { 3 if (n == 0) return 1%b; 4 long half = fastPower(a, b, n/2); 5 if (n % 2 == 0) { 6 long temp = half * half; 7 return (int)(temp % b); 8 } 9 else { 10 long temp = (half * half)%b * (a%b); 11 return (int)(temp % b); 12 } 13 } 14 };
1 class Solution { 2 /* 3 * @param a, b, n: 32bit integers 4 * @return: An integer 5 */ 6 public int fastPower(int a, int b, int n) { 7 long ret = helper(a, b, n); 8 return (int)ret; 9 } 10 11 public long helper(int a, int b, int n) { 12 if (n == 0) return 1%b; 13 long half = helper(a, b, n/2); 14 if (n % 2 == 0) { 15 return half * half % b; 16 } 17 else { 18 return ((half * half % b) * a%b)%b; 19 } 20 } 21 };
原文：http://www.cnblogs.com/EdwardLiu/p/4276829.html