前言
持续更新了
正文
问题来源
本问题来自leetcode上的372题。
问题描述
你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1:
输入: a = 2, b = [3]
输出: 8
示例 2:
输入: a = 2, b = [1,0]
输出: 1024
分析：
func superPow(a int, b []int) int {
res := 1
for _, x := range b {
res = pow(res, 10) * pow(a, x) % 1337
}
return res
}
func pow(a, b int) int {
if a == 1 || b == 0 {
return 1
}
if b % 2 == 1 {
return a * pow(a, b-1) % 1337
}
return pow(a*a%1337, b/2)
}
快速幂算法(蒙哥马利算法)
int qmi(int m, int k, int p)
{
int res = 1, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
可以用这个qmi函数替换pow函数
总结：
勤思考。
结语
不管怎么样好好加油。
