Fast Power

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

Analyse: divide and conquer. Be aware of overflow.

Runtime: 12ms

 1 class Solution {
 2 public:
 3     /*
 4      * @param a, b, n: 32bit integers
 5      * @return: An integer
 6      */
 7     int fastPower(int a, int b, int n) {
 8         // write your code here
 9         if (!a || b == 1 || n < 0) return 0;
10         if (!n && b != 1) return 1;
11         if (n == 1) return a % b;
12         
13         long temp1 = fastPower(a, b, n / 2);
14         long temp = temp1 * temp1 % b;
15         if (n % 2) temp *= a % b;
16         return (int)(temp % b);
17     }
18 };