快速冪是一個處理整數冪次的演算法,可以在 的複雜度完成任務
一般來說我們處理冪次問題 會使用以下方法:
這種方法最直觀,但是卻需要 的時間才能完成
對於數字過大的數字實在太耗時
因此我們會需要用到快速冪來處理這個問題
要解釋快速冪的原理,需要用到一個性質
每個十進制非負整數 都可以被拆解成二進制
,其中
則可寫成二進制:
舉例來說:
換種角度來看,也可以將一個數字看作有一數列
二進位就是看這數列中要取哪幾項相加才會是我要的數字
就是取該項, 就是不取該項
設今天有一個數字 ,可以先把 變成二進制的寫法
得到 。其中,
要窮舉序列 是很簡單的,只需要先計算 值,再使用 迴圈就可以實現
再來就是要來判斷 是 還是 。若 則將答案乘上去, 就不理他
可以用 迴圈來實現,這樣就不需要 值了
Zerojudge d636. 大爆炸bomb
Zerojudge d219. 00374 - Big Mod
Zerojudge k137. 次方練習
CSES Exponentiation
CSES Exponentiation II
ShanC 程式競賽筆記
作者: ShanC
更新: 2024/9/13