New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

算法：快速矩阵幂 #8

Open

MarsonShine opened this issue Jun 28, 2021 · 0 comments

Owner

MarsonShine commented Jun 28, 2021 •

edited

Loading

在知乎上对于数论之矩阵快速幂有容易看懂讲解
其主要思想就是缩短计算次数，拿上面文章中的例子：求 $a^{156}$ 的值。

如果用一般的做法，要么执行乘法的次数为 156-1=155 次乘法；而如果使用矩阵快速幂，那么实际上就是下面
$\bg_white \begin{align*}x = a^{156} &= a^{10011100} \\&= a^{2^7*1+2^6*0+2^5*0+2^4*1+2^3*1+2^2*1+2^1*0+2^0*0} \\&= (a^{2^7}*1)*(a^{2^6}*0)*(a^{2^5}*0)*(a^{2^4}*1)*(a^{2^3}*1)*(a^{2^2}*1)*(a^{2^1}*0)*(a^{2^0}*0) \\\end{align*}$
这样乘法的次数就由原来的 155 次变为现在的 $二进制的长度二进制1的个数=84=32$ 。

时间复杂度由原来的 O(n) 变为 O(log n)。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment