---
title: "快速幂"
created: 2025-11-28
tags:
  - 算法
---

# 快速幂

- [[2-Learning/02-算法/03-刷题理模型/数论相关问题/快速幂|快速幂]]

因为幂的性质

比如2^3可以转换成$2^{1+2}$也就是$2^1\* 2^2$

根据这样我们其实就可以把一个大的幂次拆解成几个小的去计算

什么东西能将x拆开成几部分 且相加起来仍是x呢

显然 用二进制

还是以3为例 3 即11 它可以拆成 两个1

而且这两个1还是有关联的 左边这个1是右边那个1的平方

那么 就可以很容易地从低位开始 递推预处理出每一部分的值

（其实只需要算出第一个 然后每往左一位就是上一次的平方）

然而不是每一位都要取的 我们只需要取是1的即可

$a^b$中设$b=2^{t1}+2^{t2}+…+2^{tk}$(二进制)

![[image-87c4124d.png]]

![[image-3ae7de18.png]]

其实意思就是$2^{12}$可以化成$2^8\*2^4$

4和8怎么来的

第一轮 $2^0$ 因为是该位的二进制为0所以不取

第二轮${2^{0}}^2$即$2^2$
为0 不取

第三轮 ${2^2}^2$即$2^4$
  为1 取

第四轮${2^4}^2$即 $2^8$
  为1 取

至于为什么可以每轮都模p

其实就是一个交换律

(a%p)*(b%p)=(a\*b)%p

所以何必要求到最大的时候统一模呢 每轮做就好了 还能防止爆数据

```cpp
int qmi(int a, int b, int p)
{
    int res = 1 % p;
    while(b)
    {
        if (b & 1)
          res = (long long)res * a % p;
        a = (long long)a * a % p;//不管是0还是1 这一位都用过了 a是不断平方的
        b>>=1;
    }
    return res;
}
```

- `a^b`

---
⬅️ [[子集|子集]] 🏠 [[00-刷题理模型]] ➡️ [[a-b|a-b]]