From d6c60e1ddaaea99c3be33d68b7bfe25badb41a29 Mon Sep 17 00:00:00 2001
From: Ir1dXD <sirius.caffrey@gmail.com>
Date: Mon, 10 Sep 2018 13:13:49 +0800
Subject: [PATCH] Update quick-pow.md

---
 docs/math/quick-pow.md | 48 ++++++++++++++++++++++++------------------------
 1 file changed, 24 insertions(+), 24 deletions(-)

diff --git a/docs/math/quick-pow.md b/docs/math/quick-pow.md
index b27ffd9e..748098d5 100644
--- a/docs/math/quick-pow.md
+++ b/docs/math/quick-pow.md
@@ -1,6 +1,6 @@
 快速幂，是一种求 $a^b \bmod p$ 的方法，得益于将指数按二进制拆开的思想。
 
-事实上，根据模运算的性质，$a \times b \bmod p = ((a \bmod p) \times b) \bmod p$。那么我们也可以把 2 $a^b \mod p$ 分解成一系列比较小的数的乘积。
+事实上，根据模运算的性质，$a \times b \bmod p = ((a \bmod p) \times b) \bmod p$。那么我们也可以把 $a^b \mod p$ 分解成一系列比较小的数的乘积。
 
 如果把 $b$ 写作二进制为 $a_ta_{t-1} \cdots a_1a_0$，那么有：
 
@@ -24,29 +24,11 @@ $$
 
 在算法竞赛中，快速幂的思想不仅用于整数乘法，也可用于大整数加法，矩阵幂运算等场合中。
 
-```c++
-int quickPow(int a, int b, int c) {
-  // calculates a^b mod c
-  int res = 1, bas = a;
-  while (b) {
-    if (b & 1) res = (LL)res * bas % c;
-    // Transform to long long in case of overflow.
-    bas = bas * bas % c;
-    b >>= 1;
-  }
-  return res;
-}
-```
-
-$a^b mod p$ 之所以费时，是因为b有多大就需要多长时间，如果b太大就会耗时太长从而gg，那能不能省一点时间呢？
-
-举个栗子，$a^{10}$ ，在普通计算机中是可以正常运算的，可是假设计算机每秒只能运行2次，在如此差的硬件条件下该怎么办呢？
-
-我们知道，$a^{10}$等价于下面的式子：
+举个栗子，$a^{10}$等价于下面的式子：
 
 $a \times a \times a \times a \times a \times a \times a \times a \times a \times a$
 
-通过观察我们不难发现，$a^{10}$可以转化成$a \times a^{5}$
+通过观察我们不难发现，$a^{10}$可以转化成$(a \times a)^{5}$
 
 $\left(a \times a \right) \times\left(a \times a \right) \times \left(a \times a \right) \times \left(a \times a \right) \times \left(a \times a \right)$
 
@@ -58,7 +40,25 @@ $\left (a' \times a'\right) \times\left (a' \times a'\right) \times a'$
 
 $a^0=1$和$a^1=a$
 
-实现代码
+## 实现代码
+
+### 非递归版
+
+```c++
+int quickPow(int a, int b, int c) {
+  // calculates a^b mod c
+  int res = 1, bas = a;
+  while (b) {
+    if (b & 1) res = (LL)res * bas % c;
+    // Transform to long long in case of overflow.
+    bas = bas * bas % c;
+    b >>= 1;
+  }
+  return res;
+}
+```
+
+### 递归版
 
 ```c++
 long long qpow(long long a,long long b,long long p)
@@ -78,6 +78,6 @@ long long qpow(long long a,long long b,long long p)
 }
 ```
 
-（为了使用[这题](https://www.luogu.org/problemnew/show/P1226)测试，全部改成了long long。）
+## 例题
 
-这样，时间复杂度就从$O(b)$降至了非常可观的指数级$O(log_2b)$
\ No newline at end of file
+模板题：[Luogu P1226](https://www.luogu.org/problemnew/show/P1226)
-- 
2.11.0