【学习笔记】光速幂

简介:

光速幂主要思想是分块,把幂分为 \(\sqrt{p}\) 份,那么 \(a^b=a^{k\sqrt p+t}\),其中 \(k,t\) 为常数,\(p\) 表示模数。\(\mathcal{O}(\sqrt p)\) 预处理出所有 \(a^{k\sqrt{p}}\) 和 \(a^t\)。然后 \(\mathcal{O}(1)\) 查询。

因为 \(b\) 可能很大,所以要模 \(\varphi(p)\)。

优缺点:

优点:

快!

缺点:

必须底数固定、模数固定。空间较大。

代码:

普通幂:

gugugu

矩阵幂:

gugugu
上一篇:微积分的总结


下一篇:2021.10做题记录