关于一种快速求幂算法

litjohn · 2024-09-26 21:56:10 · 算法·理论

假设要计算 a^b。

先算 a^{\lfloor\sqrt{b}\rfloor}，然后就变成了 O(\sqrt{b}) 的算法。（类似分块）

但是求 a^{\lfloor\sqrt{b}\rfloor} 的过程、求 (a^{\lfloor\sqrt{b}\rfloor})^{b / \lfloor\sqrt{b}\rfloor} 的过程与 a^{b \bmod \lfloor\sqrt{b}\rfloor} 的过程都可以用同样的方法递归计算，就会变得很快。

#include <bits/stdc++.h>

using namespace std;

unsigned long long mod_exp(unsigned long long a, unsigned long long b, unsigned long long p) {
    // 边界情况
    if (b == 0) {
        return 1;
    } else if (b == 1) {
        return a;
    } else if (b == 2) {
        return a * a % p;
    } else if (b == 3) {
        return ((a * a) % p * a) % p;
    }

    // 计算 sqrt(b)
    unsigned long long sqrt_b = (long long) floor(sqrt(b));

    // 递归计算 a^sqrt_b mod p
    unsigned long long res_sqrt_b = mod_exp(a, sqrt_b, p);

    // 计算 (a^sqrt_b)^(b / sqrt_b) mod p
    unsigned long long exp1 = mod_exp(res_sqrt_b, b / sqrt_b, p);

    // 计算 a^(b % sqrt_b) mod p
    unsigned long long exp2 = mod_exp(a, b % sqrt_b, p);

    // 返回最终结果 (exp1 * exp2) mod p
    return (exp1 * exp2) % p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long x, y, mod;
    cin >> x >> y >> mod;
    cout << mod_exp(x, y, mod);
    return 0;
}

经过测试，这个实现是正确的，并且与普通快速幂差不多快。

upd：可惜已经证实时间复杂度是 O(\log^{\log_2 3} b)