本文共 831 字，大约阅读时间需要 2 分钟。

快速幂算法及其优化

快速幂是一种高效计算数的幂次的方法，避免了传统方法中重复乘法的低效性。通过将指数n分解为二进制形式，快速幂可以在O(log n)的时间复杂度内完成计算。

递归实现

int qpow(int a, int n) {    if (n == 0)        return 1;    else if (n % 2 == 1)        return qpow(a, n - 1) * a;    else {        int temp = qpow(a, n / 2);        return temp * temp;    }}

非递归实现

int qpow(int a, int n) {    int ans = 1;    while (n) {        if (n & 1) {            ans *= a;        }        a *= a;        n >>= 1;    }    return ans;}

快速幂取模优化

为了应对大数计算中的性能问题，快速幂通常结合取模操作。以下是对大素数取模的快速幂实现：

#define MOD 1000000007typedef long long ll;ll qpow(ll a, ll n) {    if (n == 0)        return 1;    else if (n % 2 == 1)        return qpow(a, n - 1) * a % MOD;    else {        ll temp = qpow(a, n / 2) % MOD;        return temp * temp % MOD;    }}

快速幂算法通过将指数二进制分解，减少了计算量。其递归和非递归实现均能显著提升效率，适用于大数运算。通过取模优化，可以进一步处理大素数问题，确保计算结果在可控范围内。

转载地址：http://xsmv.baihongyu.com/