算法-快速冪

---

前置知識

• 倍增

---

思路

我們要求 $a^n$。
簡單的方法是 $a^n=a^{n?1}?a$
但是我們不妨使用倍增的思想
若 $2\mid n$，則 $a^n={a^{\frac{n}{2}}}^2$
若 $2?n$，則 $a^n={a^{?\frac{n}{2}?}}^2?a$

---

算法參數

• 時間復雜度：$O(\log n)$
• 空間復雜度：$O(1)$

---

實現代碼

• 基礎版本

int pow(int x,int y){int res=1;while (y){if (y&1) res=res*x;x=x*x;y>>=1;}return res;
}

• 取模版本

int pow(int x,int y,int M){int res=1;while (y){if (y&1) res=res*x%M;x=x*x%M;y>>=1;}return res;
}

---

練習

• P1226