網站首頁 編程語言 正文
一、什么是快速冪
快速冪算法是用來快速計算指數表達式的值的,例如 210000000,普通的計算方法 2*2*2*2…乘10000000次,如果一個數字的計算都要計算那么多次的話,那么這個程序一定是失敗的。
學完快速冪之后就可以用幾十次計算求出答案了
二、快速冪思想及實現
快速冪思想其實很簡單,就是公式的轉換
1、當指數是偶數時,我們可以讓指數除以2,底數乘以底數
2、當指數是奇數時,我們可以將指數變為奇數
例如 210
- 指數是偶數,210 = 45
- 指數是奇數,45 = 4 * 44
- 指數是偶數, 4 * 44 = 4 * 162
- 指數是偶數,4 * 162 = 4 * 2561
- 指數是奇數, 4 * 2561=4 * 256 * 2560
- 指數為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;
}
總結
原文鏈接:https://blog.csdn.net/weixin_52115456/article/details/127608433
相關推薦
- 2022-09-26 Go并發同步Mutex典型易錯使用場景_Golang
- 2022-07-25 C/C++實現線性單鏈表的示例代碼_C 語言
- 2023-06-17 Hugo?Config模塊構建實現源碼剖析_Golang
- 2022-04-17 Bootstrap typeahead自動補全插件的坑
- 2022-03-27 Redis?使用?List?實現消息隊列的優缺點_Redis
- 2022-11-05 Nginx監控模塊(vts模塊)詳解_nginx
- 2022-12-02 C語言#define定義宏的使用詳解_C 語言
- 2022-10-02 Blender?Python編程創建發光材質示例詳解_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支