@[EarthGiao](/space/show?uid=186489) 你也许没有搞懂快速幂的本质过程，建议再去重新学一遍 而不是在这里问（x
by Nicoppa @ 2019-05-15 18:40:28
快速幂原理：
将幂数二进制表示后转化为数个2的次方相加，并利用幂运算的分配律得出结果
例如：$17^{13}$
$13=1101(2)$
$13=2^3+2^2+2^0$
所以
$17^{13}=17^{(2^3+2^2+2^0)}=17^{2^3}*17^{2^2}*17^{2^0}$
by smarthehe @ 2019-05-15 18:41:48
蒟蒻尝试解释一下
假设我们求$x^{29}$
$\because 29=(11101)_2$
$\therefore x^{29}=x^{2^4}\times x^{2^3}\times x^{2^2}\times x^{2^0}$
快速幂就是模拟这个过程，把指数转化成二进制，如果（从右往左）第$y$位是$1$，那结果就要乘$x^{2^{y-1}}$
再比如$z^{47}=z^{32}\times z^8\times z^4\times z^2\times z$
就是因为$47=(101111)_2$
原理就是同底数幂相乘，底数不变质数相加，而$2^0,2^1,2^2, ...,2^{n-1}$可以表示出$1\sim 2^n-1$的所有数
（如有错误求不骂QAQ
by XiXi @ 2019-05-15 18:49:52
@[smarthehe](/space/show?uid=103732) 谢谢大佬，我想了一下午的快速幂没想明白，看你一句话就懂了，十分感谢
by EarthGiao @ 2019-05-15 19:20:02
好奇葩的问题啊 ...
就像问龟速乘为什么每次都乘2一样 ...
by aminoas @ 2019-05-15 19:20:38
@[XiXi](/space/show?uid=5057) 谢谢大佬
by EarthGiao @ 2019-05-15 19:22:15
@[baoyu](/space/show?uid=93465) 谢谢大佬
by EarthGiao @ 2019-05-15 19:25:20
@[QwQ自动机](/space/show?uid=143834) QwQ本蒟蒻笨啦
by EarthGiao @ 2019-05-15 19:27:54