快速幂(Exponentiation by squaring,平方求幂)是一种简单而有效的小算法,它可以以O(logn)
的时间复杂度计算乘方。快速幂不仅本身非常常见,而且后续很多算法也都会用到快速幂。
递归方程如下:
double qpow(double x, int n) {
if (x==0) return 0;
// int32 变量 n ∈ [-21474838, 21474837]
// 因此当n=-21474838时,如果直接n=-n,会产生越界而赋值失败,这个时候我们用long long变量存一下n,这样计算范围更广。
long long a = n;
if (a<0) {
x = 1/x;
a = -a;
}
if (a==0) return 1;
else if (a&1) {
return x*qpow(x, a-1);
}
else return qpow(x*x, a/2);
}
// 如果是大数情况下需要用到MOD
// 递归快速幂(对大素数取模)
#define MOD 1000000007
typedef long long ll;
ll qpow(ll x, ll n)
{
if (x==0) return 0;
if (n<0) {
x = 1/x;
n = -n;
}
if (n == 0)
return 1;
else if (n % 2 == 1)
return qpow(x, n - 1) * x % MOD;
else
{
return qpow(x*x, n / 2) % MOD;
}
}
double qpow1(double x, int n) {
if (x==0) return 0;
long long b = n;
if (b<0) {
x = 1/x; // 这里x是double类型,因此相除之后也是double类型
b = -b;
}
double res=1;
while (b) {
if (b&1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
// 如果是大数情况下需要用到MOD
// 非递归快速幂(对大素数取模)
#define Mod 1000000007
long long qpow2(long long x, long long n) {
if (x==0) return 0;
long long b = n;
if (b<0) {
x = 1.0/x;
b = -b;
}
long long res = 1;
while (b) {
if (b&1) {
res *= x;
res %= Mod;
}
x *= x;
x %= Mod;
b >>= 1;
}
return res;
}
以上方法是为了加快次幂运算的技巧:
以下的几行代码可以加快输入输出的速度,从而降低程序的执行耗时,可以在刷题的时候尝试加在最前,耗时能降低30%-40%
static int n=[](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- azee.cn 版权所有 赣ICP备2024042794号-5
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务