imicola 快速幂
快速幂

快速幂

321 字 · 约 1 分钟

7 快速幂

  • 不多说,先上代码
#include <bits/stdc++.h>
using namespace std;

long long fastpower(long long a , long long b)
{
    long long ans = 1;
    while (b > 0)
    {
        if (b&1)
        {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}

int main()
{
    cout << fastpower(2,8);
}
cpp

快速幂的核心思路在下面这串代码里

while (b > 0)
{
    if (b&1)
    {
        ans *= a;
    }
    a *= a;
    b >>= 1;
}
cpp
  • 快速幂的时间复杂度为O(log⁡N)O(\log{N})

知识关联

1 反向链接 · 0 提及笔记
局部关系图谱 悬停高亮 · 点击跳转