您好,欢迎来到爱站旅游。
搜索
您的当前位置:首页【C++】快速幂的递归和迭代实现及LeetCode加速代码

【C++】快速幂的递归和迭代实现及LeetCode加速代码

来源:爱站旅游

  快速幂(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

本站由北京市万商天勤律师事务所王兴未律师提供法律服务