快速幂¶
前置知识¶
递归，二进制
目标¶
递归写法，循环迭代写法
What¶
快速幂是快速计算一个数的大正整数乘幂的一般方法
递归代码¶
int qmi(int a, int k, int p)
{
if (k == 0) return 1;
int t = qmi(a, k / 2, p);
if (k & 1) return 1ll * t * t * a % p;
else return 1ll * t * t % p;
}
循环迭代代码¶
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = 1ll * res * a % p;
k >>= 1;
a = 1ll * a * a % p;
}
return res;
}
总结¶
快速幂的计算，注意中间过程，可能会爆int，要格外注意
拓展：快速加，矩阵快速幂