APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

C++快速幂

2018年2月28日 1320点热度 0人点赞 0条评论

前言

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。

C++的实现方式:

先笔记一下:

b & 1  //取b二进制的最低位,判断和1是否相同,相同返回1,否则返回0,可用于判断奇偶(偶数二进制结尾是0奇数是1)
b>>1   //把b的二进制右移一位,即去掉其二进制位的最低位 就是b=b/2

递归的方式

long long  pow(long long a,long long b){
  if (b==0) return 1;
  long long temp=pow(a,b>>1);
  temp=temp*temp%MOD;
  if (b&1) temp=temp*a%MOD;
  return temp%MOD;
}

非递归的方式

long long power(long long a,long long b){
	long long t=1,y=a;
	while(b){
		if (b&1==1) t=t*y%k;
        y=y*y%k;
		b=b/2;
  }
  return t; 
}

标签: C++ 分治算法 快速幂
最后更新:2018年2月28日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
#C/C++#数据结构:ST表模板 Google空间(XSpace)自动配置谷歌框架/直连谷歌商店 《サクラノ詩》VI 章 直哉与蓝对话 《从零》第二季&《春物》第三季制作决定 C/C++字符串哈希(单哈希)Hash算法 模板 本博客黑白一周以悼念京都动画及遇难者
标签聚合
C++ OI 动漫 洛谷 日常 HTML C/C++ ST
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang