# [372. Super Pow](https://leetcode.com/problems/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 就结果快速幂求解。