【C++/算法】快速冪算法詳解
2023-08-05 09:07 作者:還要學(xué)習(xí)三年 | 我要投稿
1、數(shù)字溢出怎么辦？
?
02:38
?
使用取模運(yùn)算性質(zhì)：
(a * b) % p = [(a % p) * (b % p)] % p
?
03:03
?
2、證明模運(yùn)算性質(zhì)的過(guò)程中為什么要設(shè)定？
a = k1 * p + q1
b = k2 * p + q2
?
03:17
?
這里我自己補(bǔ)充下作者的證明。
為了證明 (a * b) % p = (a % p * b % p )% p，
我們需要先證明 a % p * b % p 的值在模 p 的意義下等于 a * b 的值在模 p 的意義下。
設(shè) a mod p = q1，b mod p = q2，
那么：
a = k1 * p + q1
b = k2 * p + q2
其中 k1 和 k2 是任意整數(shù)。
所以，
a*b = (k1*k2*p + k1*q2 + k2*q1)*p + q1*q2
然后取模：
(a * b) % p = (q1 * q2) % p
其中：
(k1*k2*p + k1*q2 + k2*q1)*p 為 0，被直接消去了。因?yàn)樵擁?xiàng)是 p 的倍數(shù)。
又：
a = k1 * p + q1
b = k2 * p + q2
則：
a % p = q1
b % p = q2
進(jìn)而：
q1 * q2 = a % p * b % p
所以在模 p 的意義下：
(a * b) % p = [(a % p) * (b % p)] % p
3、快速冪原理？
底數(shù)平方，指數(shù)除以2。
將 O(n) 的時(shí)間復(fù)雜度，轉(zhuǎn)換成 O(log) 級(jí)別的時(shí)間復(fù)雜度。
標(biāo)簽：
