APTX博客

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

C++快速幂

2018年2月28日 1677点热度 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
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
几种云端 VSCode/类 VSCode 方案对比与部署 C/C++ 最短路算法Dijkstra算法 + 堆优化模板 #万事达活动#免费10元话费不限运营商 Star Divine C/C++线性筛素数的三种方法 恭喜四叶小天使取得最后的胜利
标签聚合
C++ 洛谷 日常 HTML C/C++ ST 动漫 OI
分类目录
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang