返回主页

快速幂

计算 a 的 b 次幂对 m 取模的结果，时间复杂度 O(log b)

算法模板发布于 2026/08/21#快速幂
C++22 行393 Bytes
下载文件
using ll = long long;
ll quick_pow(ll a, ll b, ll m) {
    ll ans = 1 % m;
    ll w = a;
    while (b) {
        if (b % 2 == 1) ans = ans * w % m;
        w = w * w % m;
        b /= 2;
    }
    return ans;
}

// 位运算版
ll qpow(ll a, ll b, ll p) {
    ll ans = 1 % p;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}