Calculate the a^n % b where a, b and n are all 32bit integers.ExampleFor 2^31 % 3 = 2For 100^1000 % 1000 = 0ChallengeO(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 };