基本用法

分析

求\(a^kmod p\)的问题

先研究这个\(a^k\)以\(2^5\)为例

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

while(k--) res*=2;

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

#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

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\)的形式做个优化……

⬅️ 快速幂 🏠 00-刷题理模型 ➡️ 序列的第k个数

基本用法

分析

题目

💬 评论