快速幂
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
简介快速幂是能快速计算一个幂的方案,他可以作用于所有满足结合律、封闭性的二元运算,即半群
定义不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时,不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$
快速幂核心思想在半群中,只要$k=u+v$一定有$x^k=x^u\circ x^v$.
所以我们可以把k看作一个二进制数,把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$
这里最多分解为$\log_2(k)$个元素,而且每个元素可以由前k个元素获取,所以只需要进行$log_2(k)$次二元计算即可的到最终答案。
阅读全文…