From f92d22b17625fc2b8ba4bfb16da596df7f3ec9cc Mon Sep 17 00:00:00 2001 From: Trisolaris HD <36555123+TrisolarisHD@users.noreply.github.com> Date: Sun, 5 May 2019 12:59:32 +0800 Subject: [PATCH] Update quick-pow.md --- docs/math/quick-pow.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/math/quick-pow.md b/docs/math/quick-pow.md index dee17313..9873ddf8 100644 --- a/docs/math/quick-pow.md +++ b/docs/math/quick-pow.md @@ -20,7 +20,7 @@ $$ 根据上式我们发现,原问题被我们转化成了形式相同的子问题的乘积。 -最重要的是,我们注意到, $a^{2^{i+1}} \bmod c = (a^{2^i})^2 \bmod c$ ,可以再常数时间内从 $2^i$ 项推出 $2^{i+1}$ 项。于是,原问题总的复杂度就是 $O(\log b)$ +最重要的是,我们注意到, $a^{2^{i+1}} \bmod c = (a^{2^i})^2 \bmod c$ ,可以在常数时间内从 $2^i$ 项推出 $2^{i+1}$ 项。于是,原问题总的复杂度就是 $O(\log b)$ 在算法竞赛中,快速幂的思想不仅用于整数乘法,也可用于大整数加法,矩阵幂运算等场合中。 -- 2.11.0