---
title: "基本用法"
created: 2025-11-28
tags:
  - 算法
---

# 基本用法

## 分析

求$a^kmod p$的问题

先研究这个$a^k$以$2^5$为例

暴力的写法肯定是循环做5次乘2

`while(k--) res*=2;`

时间复杂度在这个指数上 一组数据是$O(n)$ n组数据那就是
$O(n^2)$了

```cpp
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin>>n;
    while(n--){
        int a,k,p;
        cin>>a>>k>>p;
        long long res=1;
        while(k--)
            res=res*a%p;
        cout<<res<<endl;
    }

    return 0;
}
```

考虑优化

幂运算有什么性质呢？

印象里好像有个什么$a^{(b+c)}=a^b\*a^c$

$2^5=2^{(2+3)}=2^2\*2^3$

嗯没问题

这其实又是类似dp的思路 对于每个问题我都直接硬算求解肯定是很浪费时间的

如果我每个问题求完后 把它的结果利用起来 然后对于一个新问题 可以用这些已有的答案快速推导出来

那么问题变成了 我要想办法 并且是稳定且通用的方法 把一个形如 $a^b$ 的数
转变成 $a^{(c+d+…+f)}$的形式

巧妙的地方就来了 利用二进制

首先我们知道 每一个十进制的数都能用二进制表示

比如5 → 101

对于101我们很容易拆解了吧

最后一位拿出来 1 第二位 00 最高位 100

二进制1 → 十进制 1

二进制100 → 十进制 4

5=1+4

$2^5 = 2^{(1+4)}=2\*2^4$

没问题

整理一下 把指数 k 当成二进制进行处理

预处理出$a^{2^0}$ ,$a^{2^1}$ ,
$a^{2^2}$,  …,  $a^{2^{log\_k}}$这k个数

将$a^k$用$a^{2^0}$,
$a^{2^1}$,$a^{2^2}$,…,$a^{2^{log\_k}}$这k种数来组合

如何组合（判断某位用不用？） 某位为1 就用 为0 就不用

两个问题

1、如何预处理出来$a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log\_k}}$

2、如何取得处理k的每一位

1、$a^{2^0},a^{2^1},a^{2^2},…,a^{2^{log\_k}}$的每一位都是前一位\*a
而每一次只需要用到上一次的结果

所以没必要把所有的数都存下来 只需要用一个变量a 这个a每轮不管被没被选 都累乘上a

2、二进制里学过 直接k不断取得最后一位 然后划掉最后一位 `while(k) if(k&1) …; k>>=1;`

很容易得到模板 y氏幽默：中西合璧 quick 幂 ==qmi

```cpp
long long qmi(long long a,int k,int p){ //注意a要传入long long  a是指数级增长的 容易爆int
    long long res=1%p;  //防止p=1 res=1%1=0 而不是 1
    while(k){
        if(k&1)
           res=res*a%p;
        k>>=1;
        a=a*a%p;   //不传long long 的话 这里用 a=(long long)a*a%p;
    }
    return res;
}
```

时间复杂度：$O(n∗log\_b)$

## 题目

快速求$a^k mod p$

之前二进制里 二进制优化问题里提到过这个快速幂算法 这里再系统学一下 刷几道题

……哪是简单考快速幂 都是问题分析完后发现有这个$a^kmodp$的形式 做个优化……

- [[序列的第k个数|序列的第k个数]]
- [[越狱|越狱]]

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/数论相关问题/快速幂|快速幂]] 🏠 [[00-刷题理模型]] ➡️ [[序列的第k个数|序列的第k个数]]