tk's blog
  • tk's blog Read Me
  • 算法相关
    • 数据结构
      • 【集训整理】 旋转treap模板
      • 二叉树及相关数据结构的java语言实现
      • 快乐树0x01:AVL树的java实现
      • 快乐树0x02 线段树实现(c++)
      • 链表的Java语言实现
    • 算法
      • DP的背包问题小结-java语言描述
      • 【集训整理】2-SAT问题 模板题
      • 【集训整理】Tarjan算法 模板题
      • 【集训整理】差分约束 模板题
      • 【集训整理】最近公共祖先LCA 模板题
      • 二分查找与二分答案-java实现
      • 动态规划-java语言练习一:暴力DP
      • 快速幂
      • 状态压缩DP-java描述
      • 差分
      • 乘法逆元
    • 题解
      • CFRound-GoodBye2022题解
  • java相关
    • Java与算法竞赛——注意事项摘录
    • java面向对象简要总结 一
    • java面向对象简要总结 三
    • java面向对象简要总结 二
  • 后端相关
    • Linux-Crontab命令
    • Spring Data JPA 使用方法
    • Spring集成Artemis实现JSM的异步消息传递
    • Spring使用自定义配置项
    • MIT6.824分布式系统Lab1.MapReduce笔记
    • MIT6.824分布式系统Lab2-Raft-A笔记
    • MIT6.824分布式系统Lab2-Raft-B笔记
  • 杂谈
    • 杂谈-关于2021
  • 杂项
    • c语言 scanf的返回值
    • 系统设计
  • 计科基础
    • 编译原理
      • 编译原理:词法分析笔记
    • CSAPP 第二章笔记
    • 计算机组成原理笔记
    • CSAPP Lab1. Datalab
    • CSAPP Lab2 Bomblab
  • C++每日一题
    • C++每日一题 Day 1 肥宅水
    • C++每日一题 Day 2 数字反转
    • C++每日一题 Day 3 理五的凡尔赛风气
    • C++每日一题 Day 4 我喜欢这个数
    • C++每日一题 Day 5 数字楼梯
    • C++每日一题 Day 6 插火把
    • C++每日一题 Day 7 贪吃蛇
    • C++每日一题 Day 8 蒙德最强战力
    • C++每日一题 Day 9 璃月七星选举
    • C每日一题 Day 2 肥宅水
    • C每日一题 Day 3 理五的凡尔赛风气
    • C语言每日一题 Day 1 荧妹好感队
由 GitBook 提供支持
在本页
  1. 算法相关
  2. 算法

快速幂

上一页动态规划-java语言练习一:暴力DP下一页状态压缩DP-java描述

最后更新于1年前


快速幂用于快速计算指数(2n2^n2n),主要思想是二分。

由于计算机计算单个乘法比多个乘法快得多,所以利用二分的思想来减少乘法运算次数可以提高速度。

例:710=7∗7∗7∗...∗77^{10} = 7*7*7*...*7710=7∗7∗7∗...∗7 需要计算9次乘法,而先计算757^575再计算7107^{10}710,就只用计算75=7∗7∗7∗7∗77^5 = 7*7*7*7*775=7∗7∗7∗7∗7和710=75∗757^{10}=7^5*7^5710=75∗75,只用5次乘法。

以此类推,得到一个递归二分的策略:

n是奇数:an=an−1∗ann是偶数:an=an/2∗an/2n=0:an=1n是奇数:a^n = a^{n-1}*a^n\\ n是偶数:a^n = a^{n/2}*a^{n/2}\\ n=0:a^n = 1n是奇数:an=an−1∗ann是偶数:an=an/2∗an/2n=0:an=1

写成代码:

typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        ll temp = qpow(a, n / 2);
        return temp * temp;
    }
}

这是递归版本的快速幂。 可以看到,这里二分的操作可以和二进制的右移对应,于是可以用二进制的方式理解:

由于上面的递归形式递归会耗费时间,所以用二进制的思路将上面的递归改成循环形式会更好。

代码:

int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

710=7[1010]27^{10} =7^{[1010]_2}710=7[1010]2​ ,于是710=7[1000]2∗7[0010]27^{10}=7^{[1000]_2} * 7^{[0010]_2}710=7[1000]2​∗7[0010]2​

具体方法:由于每个二进制位表示一次平方,所以我们对n的每个二进制位,让底数进行一次自乘,如果对应的二进制位为1,则将此时的底数乘给ans,达到例如 7[1010]2=7[1000]2∗7[0010]27^{[1010]_2}=7^{[1000]_2} * 7^{[0010]_2}7[1010]2​=7[1000]2​∗7[0010]2​的效果。