APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

C++快速幂

2018年2月28日 1529点热度 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; 
}

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ 分治算法 快速幂
最后更新:2018年2月28日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
人民邮电出版社社庆:Kindle亚马逊免费领取8本书 #模板分享#我永远喜欢加藤惠个人主页HTML模板 好耶!是五等分的漫画 34.1G图片图包Ondrive/GDrive分流 #洛谷#C/C++P1082 同余方程 逆元(欧拉函数)/拓展欧几里得 #动漫#《学园孤岛》OP/ED/角色歌下载
标签聚合
C/C++ 洛谷 C++ 日常 OI HTML 动漫 ST
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang