快速冪問題
即求：\(a^b \mod c\)
暴力
直接暴力
時間復雜度：\(O(b)\)
int ans = 1,i;
for(i=0;i<b;i++)
ans *= a;
ans %= c;
問題在于當a，b過大時，容易溢位，
優化溢位
時間復雜度：\(O(b)\)
首先明確2個公式：
- \(a^b \mod c = [(a \mod c)^b] \mod c\)
- \((a*b) \mod c = [(a \mod c)*(b \mod c)] \mod c\)
即：積的取余等于取余的積的取余！
證明：
設：\(d = a \mod c, e = b \mod c\)
則：\(a = t*c+d, b = k*c+e\)
可以推出：
公式1可由公式2推得，
int ans = 1,i;
a %= c;
for(i=0;i<b;i++)
ans *= a;
ans %= c;
這個改進不大，只是減小了資料溢位的可能，
快速冪
時間復雜度：\(O(\log_2{b})\)
公式：
\[a^b \mod c = (a^2)^ \left( b/2 \right) \mod c, 當b為偶 \]\[a^b \mod c = ((a^2)^ \left( b/2 \right) * a) \mod c, 當b為奇 \]依據上述兩個公式，令\(k = a^2 \mod c\)，我們可以得出如下結論：
- 當b是偶數，即求\(k^{b/2} \mod c\)
- 當b是奇數，即求\(((k^{b/2} \mod c) * a) \mod c\)
每次用此公式迭代即為快速冪取余演算法！
int ans = 1;
a %= c;
while(b>0)
{
if(b%2==1) ans = (ans *a)%c;
b /= 2;
a = (a*a)%c;
}
看了演算法競賽（劉汝佳）之后發現還有一種寫法，思想相同，用遞回實作，代碼：
int pow_mod(int a,int b,int c)
{
if(b==0) return 1;
int x = pow_mod(a,b/2,c);
long long ans = (long long)x * x % c;
if(b%2==1) ans = ans * a % c;
return (int)ans;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288791.html
標籤：其他
上一篇：如何自動化測驗