快速冪及其模

前提

typedef long long int ll;

快速冪

時間復雜度

• O(log2(N))

原理

冪指數以二進制的形式參與計算

然后把a^b轉化為 通項為 a^( 2^n(0或1)) 求0到n項和的多項式

代碼

ll quick_pow(ll a, ll b) {ll res = 1;while (b){if (b & 1)res = res * a;a *= a;b /= 2;}return res; }

快速冪的模

原理

由模運算a^b%p = ((a%p)^b)%p結合快速冪的原理得出

代碼

ll quick_pow_mod(ll a, ll b, ll mod) {ll res = 1;while (b){if (b & 1)res = res * a % mod;a = a * a % mod;b /= 2;}return res; }

總結

以上是生活随笔為你收集整理的快速幂及其模的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。