-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
372. Super Pow.go
58 lines (55 loc) · 1.81 KB
/
372. Super Pow.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
// 模运算性质五:ab % p = ((a % p) * ( b % p)) % p, 其中 ab 是一个数字,如:2874,98374 等等
// 举个例子
// 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
}