快速冪及其模
前提
typedef long long int ll;
快速冪
時(shí)間復(fù)雜度
- O(log2(N))
原理
冪指數(shù)以二進(jìn)制的形式參與計(jì)算
然后把a(bǔ)^b轉(zhuǎn)化為 通項(xiàng)為 a^( 2^n(0或1)) 求0到n項(xiàng)和的多項(xiàng)式
代碼
ll quick_pow(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a;
a *= a;
b /= 2;
}
return res;
}
快速冪的模
原理
由模運(yùn)算a^b%p = ((a%p)^b)%p結(jié)合快速冪的原理得出
代碼
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;
}
