372. Super Pow

题目

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

题目大意

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

解题思路

求 a^b mod p 的结果，b 是大数。

这一题可以用暴力解法尝试。需要用到 mod 计算的几个运算性质：

  模运算性质一：(a + b) % p = (a % p + b % p) % p
  模运算性质二：(a - b) % p = (a % p - b % p + p) % p
  模运算性质三：(a * b) % p = (a % p * b % p) % p
  模运算性质四：a ^ b % p = ((a % p)^b) % p

这一题需要用到性质三、四。举个例子：

  12345^678 % 1337 = (12345^670 * 12345^8) % 1337
  				 = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337  ---> 利用性质 三
  			     = (((12345^67)^10 % 1337) * (12345^8 % 1337)) % 1337  ---> 乘方性质
                   = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337  ---> 利用性质 四
  				 = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337  ---> 反向利用性质 三

经过上面这样的变换，把指数 678 的个位分离出来了，可以单独求解。继续经过上面的变换，可以把指数的 6 和 7 也分离出来。最终可以把大数 b 一位一位的分离出来。至于计算 a^b 就结果快速幂求解。

Uh oh!