# Fast Power ### Source - lintcode: [(140) Fast Power](http://www.lintcode.com/en/problem/fast-power/) ### 題解 數學題，考察整數求模的一些特性，不知道這個特性的話此題一時半會解不出來，本題中利用的關鍵特性為： ~~~ (a * b) % p = ((a % p) * (b % p)) % p ~~~ 即 a 與 b 的乘積模 p 的值等于 a, b 分別模 p 相乘后再模 p 的值，只能幫你到這兒了，不看以下的答案先想想知道此關系后如何解這道題。 首先不太可能先把 ana^nan 具體值求出來，太大了... 所以利用以上求模公式，可以改寫 ana^nan 為： an=an/2?an/2=an/4?an/4?an/4?an/4?=...a^n = a^{n/2} \cdot a^{n/2} = a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot = ...an=an/2?an/2=an/4?an/4?an/4?an/4?=... 至此遞歸模型建立。 ### Python ~~~ class Solution: """ @param a, b, n: 32bit integers @return: An integer """ def fastPower(self, a, b, n): if n == 1: return a % b elif n == 0: # do not use `1` instead `1 % b` because `b = 1` return 1 % b elif n < 0: return -1 # (a * b) % p = ((a % p) * (b % p)) % p product = self.fastPower(a, b, n / 2) product = (product * product) % b if n % 2 == 1: product = (product * a) % b return product ~~~ ### C++ ~~~ class Solution { public: /* * @param a, b, n: 32bit integers * @return: An integer */ int fastPower(int a, int b, int n) { if (1 == n) { return a % b; } else if (0 == n) { // do not use 1 instead (1 % b)! b = 1 return 1 % b; } else if (0 > n) { return -1; } // (a * b) % p = ((a % p) * (b % p)) % p // use long long to prevent overflow long long product = fastPower(a, b, n / 2); product = (product * product) % b; if (1 == n % 2) { product = (product * a) % b; } // cast long long to int return (int) product; } }; ~~~ ### Java ~~~ class Solution { /* * @param a, b, n: 32bit integers * @return: An integer */ public int fastPower(int a, int b, int n) { if (n == 1) { return a % b; } else if (n == 0) { return 1 % b; } else if (n < 0) { return -1; } // (a * b) % p = ((a % p) * (b % p)) % p // use long to prevent overflow long product = fastPower(a, b, n / 2); product = (product * product) % b; if (n % 2 == 1) { product = (product * a) % b; } // cast long to int return (int) product; } }; ~~~ ### 源碼分析 分三種情況討論 n 的值，需要特別注意的是`n == 0`，雖然此時 a0a^0a0 的值為1，但是不可直接返回1，因為`b == 1`時應該返回0，故穩妥的寫法為返回`1 % b`. 遞歸模型中，需要注意的是要分 n 是奇數還是偶數，奇數的話需要多乘一個 a, 保存乘積值時需要使用`long`型防止溢出，最后返回時強制轉換回`int`。 ### 復雜度分析 使用了臨時變量`product`，空間復雜度為 O(1)O(1)O(1), 遞歸層數約為 logn\log nlogn, 時間復雜度為 O(logn)O(\log n)O(logn), 棧空間復雜度也為 O(logn)O(\log n)O(logn). ### Reference - [Lintcode: Fast Power 解題報告 - Yu's Garden - 博客園](http://www.cnblogs.com/yuzhangcmu/p/4174781.html) - [Fast Power 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/fast-power/)