c++入门必学算法之快速幂思想及实现

2023-10-28 17:25:35

一、什么是快速幂

快速幂算法是用来快速计算指数表达式的值的，例如 210000000,普通的计算方法 2*2*2*2…乘10000000次，如果一个数字的计算都要计算那么多次的话，那么这个程序一定是失败的。

学完快速幂之后就可以用几十次计算求出答案了

二、快速幂思想及实现

快速幂思想其实很简单，就是公式的转换

1、当指数是偶数时，我们可以让指数除以2，底数乘以底数

2、当指数是奇数时，我们可以将指数变为奇数

例如 2¹⁰

指数是偶数，2¹⁰ = 4⁵
指数是奇数，4⁵ = 4 * 4⁴
指数是偶数， 4 * 4⁴ = 4 * 16²
指数是偶数，4 * 16²= 4 * 256¹
指数是奇数， 4 * 256¹=4 * 256 * 256⁰
指数为0时停止，那么答案就是计算 4 * 256 = 1024

下面代码就是模拟这个过程：

 #include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
long long fpow(long long a,long long b){//a是底数，b是指数
	long long ans=1;//初始化答案为1
	while(b){//当指数不为0时执行
		if(b%2==0){//指数为偶数时，指数除以2，底数乘以2
			b/=2;
			a*=a;
		}else{//指数为奇数时，分离指数，ans乘以底数
			ans*=a;
			b--;
		}
	}
	return ans;//ans就是答案
}
int main(){
	long long n,m;
	cin>>n>>m;
	cout<<fpow(n,m)<<endl;
}

3、快速幂精简模板

#include<iostream>
using namespace std;
long long fpow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans*=a;
		b>>=1;
		a*=a;
	}
	return ans;
}
int main(){
	long long n,m;
	cin>>n>>m;
	cout<<fpow(n,m)<<endl;
}

总结

到此这篇关于c++入门必学算法之快速幂思想及实现的文章就介绍到这了,更多相关c++快速幂算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++快速幂与大数取模算法示例

一.快速幂其实就是求(a^b)% p ,(其中a,b,p都比较大在int范围内)这类问题. 首先要知道取余的公式: (a*b)%p=(a%p*b%p)%p . 那么幂不就是乘机的累积吗,由此给出代码: int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) /如果幂b是奇数多乘一次,因为后边会除2变偶数,(7/2=3) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2;
新手小白入门必学JAVA面向对象之多态

目录 1. 概念 2 . 特点 3. 练习:多态入门案例 4. 多态的好处 5. 多态的使用 6. 练习:多态成员使用测试 7 拓展 7.1 设计汽车综合案例 7.2 多态为了统一调用标准 7.3 静态变量和实例变量的区别 7.4 向上转型和向下转型总结 1. 概念多态是面向对象程序设计(OOP)的一个重要特征,指同一个实体同时具有多种形式,即同一个对象,在不同时刻,代表的对象不一样,指的是对象的多种形态. 可以把不同的子类对象都当作父类来看,进而屏蔽不同子类对象之间的差异,写出通用的代码,
C语言快速幂取模算法小结

本文实例汇总了C语言实现的快速幂取模算法,是比较常见的算法.分享给大家供大家参考之用.具体如下: 首先,所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求一个幂式的模(余).在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快.计算范围更大的算法,产生了快速幂取模算法.我们先从简单的例子入手:求abmodc 算法1.直接设计这个算法: int ans = 1; for(int i = 1;i<=b;i++) { ans = ans * a; } ans = ans %
sencha ext js 6 快速入门(必看)

Sencha Ext JS号称是目前世界上最先进和最强大的.支持多平台多设备的JavaScript应用程序开发框架.首先看一下Ext JS的发展简史. 1 Ext JS发展简史 1.YUI-Ext的作者Jack Slocum(杰克.斯洛克姆)打算对基于BSD协议的Yahoo User Interface (YUI)库进行自定义的扩展,但后来一度风头盖过其父辈YUI: 2.在2006年底,YUI-Ext被简化为Ext,反映了它作为一个框架的成熟和独立.该公司成立于2007年初,Ext现在为双执照,
Java语言实现快速幂取模算法详解

快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的,在整个计算过程中最麻烦的就是我们的5^1003这个过程缺点1:在我们在之后计算指数的过程中,计算的数字不都拿得增大,非常的占用我们的计算资源(主要是时间,还有空间) 缺点2:我们计算的中间过程数字大的恐怖,我们现有的计算机是没有办法记录这么长的数据的,所以说我们必须要想一个更加高效的方法来解决这个问题当我们计算AB%C的时候,最便捷的方法就是调用Ma
JavaScript基础教程——入门必看篇

JavaScript他是一种描述性语言,其实他并不难学,只要用心学,一定会学好,我相信大家在看这篇文章的时候,一定也学过HTML吧,使用JavaScript就是为了能和网页有更好的交互,下面切入主题. 一. JavaScript 1.什么是JavaScript JavaScript是一种描述性语言,也是一种基于对象(Object)和事件驱动(Event Driven)的,并具有安全性的脚本语言. 2.JavaScript的特点 JavaScript主要用来向HTML页面添加交互行为. JavaS
Python 3.8 新功能大揭秘【新手必学】

最新版本的Python发布了!今年夏天,Python 3.8发布beta版本,在2019年10月14日,第一个正式版本已准备就绪.现在,我们都可以开始使用新功能并从最新改进中受益. Python 3.8是Python语言的最新版本,它适合用于编写脚本.自动化以及机器学习和Web开发等各种任务.现在Python 3.8已经进入官方的beta阶段,这个版本带来了许多语法改变.内存共享.更有效的序列化和反序列化.改进的字典和更多新功能. 好了,正文开始,一起看看吧! Python 3.8 是 Pyth
C语言编程入门必背的示例代码整理大全

目录一.C语言必背代码前言二.一部分C语言必背代码一.C语言必背代码前言对于c语言来说,要记得东西其实不多,基本就是几个常用语句加一些关键字而已.你所看到的那些几千甚至上万行的代码,都是用这些语句和关键词来重复编写的.只是他们逻辑功能不一样,那如何快速的上手C语言代码,建议多看多写,下面是小编整理的C语言必背代码. 二.一部分C语言必背代码 1.输出9*9成法口诀,共9行9列,i控制行,j控制列. #include "stdio.h" main() {int i,j,resul
Python实现求解斐波那契第n项的解法(包括矩阵乘法＋快速幂)

斐波那契数列首先我们来定义一下斐波那契数列: 即数列的第0项: 算法一:递归递归计算的节点个数是O(2ⁿ)的级别的,效率很低,存在大量的重复计算. 比如: f(10) = f(9) + f(8) f(9) = f(8) + f(7) 重复 8 f(8) = f(7) + f(6) 重复 7 时间复杂度是O(2ⁿ),极慢 def F1(n): if n <= 1: return max(n, 0) # 前两项 return F1(n-1)+F1(n-2) # 递归算法二:记忆化搜索开一个大
详谈Ubuntu PowerShell(小白入门必看教程)

早在去年八月份PowerShell就开始开源跨平台了,但是一直没有去尝试,叫做PowerShell Core. 这里打算简单介绍一下如何安装和简单使用,为还不知道PowerShell Core on Ubuntu的同学们提供一点小小的入门帮助,谢谢大家支持~ PowerShell Core是由Microsoft开发的运行在.Net Core上的开源跨平台的任务自动化和配置管理系统. 1.在Ubuntu 16.04上安装PowerShell Core a)导入公共存储库GPG秘钥 curl htt

c++入门必学算法之快速幂思想及实现

目录

一、什么是快速幂

二、快速幂思想及实现

总结

相关推荐

随机推荐