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 就结果快速幂求解。