mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
58 lines
1.8 KiB
Go
58 lines
1.8 KiB
Go
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
|
||
}
|