因为当指数很大的时候,暴力的求幂函数的方式导致复杂度非常高。因此要采用降低复杂度的方式,如何减少复杂度,就是减少累乘的次数,这种称作快速幂。复杂度都是log2N。
typedef long long LL;
//递归写法
LL binarypow1(LL a, LL b, LL m)
{
if (b == 0)
return 1;
if (b % 2 == 1)
return a * binarypow1(a, b - 1, m) % m;
else
{
LL mul = binarypow1(a, b / 2, m);
return mul * mul % m;
}
}
//迭代写法
LL binarypow2(LL a, LL b, LL m)
{
LL ans = 1;
while (b > 0)
{
if (b & 1)
{
ans = ans * a % m;
}
a = a * a % m;
b >>=1;
}
return ans;
}
本文地址:https://blog.csdn.net/bbwqsb/article/details/107281643
如对本文有疑问, 点击进行留言回复!!
Postgresql结合postgis使用java的JDBC连接
网友评论