Fast Power

Question

题解

数学题，考察整数求模的一些特性，不知道这个特性的话此题一时半会解不出来，本题中利用的关键特性为：

  1. (a * b) % p = ((a % p) * (b % p)) % p

即 a 与 b 的乘积模 p 的值等于 a, b 分别模 p 相乘后再模 p 的值，只能帮你到这儿了，不看以下的答案先想想知道此关系后如何解这道题。

首先不太可能先把 a^n 具体值求出来，太大了… 所以利用以上求模公式，可以改写 a^n 为：

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 = …

至此递归模型建立。

Python

  1. class Solution:
  2.     """
  3.     @param a, b, n: 32bit integers
  4.     @return: An integer
  5.     """
  6.     def fastPower(self, a, b, n):
  7.         if n == 1:
  8.             return a % b
  9.         elif n == 0:
  10.             # do not use `1` instead `1 % b` because `b = 1`
  11.             return 1 % b
  12.         elif n < 0:
  13.             return -1
  15.         # (a * b) % p = ((a % p) * (b % p)) % p
  16.         product = self.fastPower(a, b, n / 2)
  17.         product = (product * product) % b
  18.         if n % 2 == 1:
  19.             product = (product * a) % b
  21.         return product

C++

  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.         if (1 == n) {
  9.             return a % b;
  10.         } else if (0 == n) {
  11.             // do not use 1 instead (1 % b)! b = 1
  12.             return 1 % b;
  13.         } else if (0 > n) {
  14.             return -1;
  15.         }
  17.         // (a * b) % p = ((a % p) * (b % p)) % p
  18.         // use long long to prevent overflow
  19.         long long product = fastPower(a, b, n / 2);
  20.         product = (product * product) % b;
  21.         if (1 == n % 2) {
  22.             product = (product * a) % b;
  23.         }
  25.         // cast long long to int
  26.         return (int) product;
  27.     }
  28. };

Java

  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.         if (n == 1) {
  8.             return a % b;
  9.         } else if (n == 0) {
  10.             return 1 % b;
  11.         } else if (n < 0) {
  12.             return -1;
  13.         }
  15.         // (a * b) % p = ((a % p) * (b % p)) % p
  16.         // use long to prevent overflow
  17.         long product = fastPower(a, b, n / 2);
  18.         product = (product * product) % b;
  19.         if (n % 2 == 1) {
  20.             product = (product * a) % b;
  21.         }
  23.         // cast long to int
  24.         return (int) product;
  25.     }
  26. };

源码分析

分三种情况讨论 n 的值，需要特别注意的是n == 0，虽然此时 a^0 的值为1，但是不可直接返回1，因为b == 1时应该返回0，故稳妥的写法为返回1 % b.

递归模型中，需要注意的是要分 n 是奇数还是偶数，奇数的话需要多乘一个 a, 保存乘积值时需要使用long型防止溢出，最后返回时强制转换回int。

复杂度分析

使用了临时变量product，空间复杂度为 O(1), 递归层数约为 \log n, 时间复杂度为 O(\log n), 栈空间复杂度也为 O(\log n).

Reference