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 就结果快速幂求解。
代码 #
package leetcode
// 解法一 快速幂 res = res^10 * qpow(a, b[i])
// 模运算性质一：(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 ---> 反向利用性质 三
func superPow(a int, b []int) int {
res := 1
for i := 0; i < len(b); i++ {
res = (qpow(res, 10) * qpow(a, b[i])) % 1337
}
return res
}
// 快速幂计算 x^n
func qpow(x, n int) int {
res := 1
x %= 1337
for n > 0 {
if (n & 1) == 1 {
res = (res * x) % 1337
}
x = (x * x) % 1337
n >>= 1
}
return res
}
// 解法二 暴力解法
// 利用上面的性质，可以得到：a^1234567 % 1337 = (a^1234560 % 1337) * (a^7 % 1337) % k = ((((a^123456) % 1337)^10)% 1337 * (a^7 % 1337))% 1337;
func superPow1(a int, b []int) int {
if len(b) == 0 {
return 1
}
last := b[len(b)-1]
l := 1
// 先计算个位的 a^x 结果，对应上面例子中的 (a^7 % 1337)% 1337
for i := 1; i <= last; i++ {
l = l * a % 1337
}
// 再计算除去个位以外的 a^y 的结果，对应上面例子中的 (a^123456) % 1337)
temp := superPow1(a, b[:len(b)-1])
f := 1
// 对应上面例子中的 (((a^123456) % 1337)^10)% 1337
for i := 1; i <= 10; i++ {
f = f * temp % 1337
}
return f * l % 1337
}