【学习笔记】光速幂
哦哦哦今天才了解到这个神秘科技
只有在底数和模数相同的情况下才能用。
预处理出\(a^1,a^2,a^3...a^s\)和\(a^{2s},a^{3s},a^{4s}...\)那么类似BSGS可以\(O(1)\)出结果。
预处理复杂度\(\sqrt{p}\)。
哦哦哦今天才了解到这个神秘科技
只有在底数和模数相同的情况下才能用。
预处理出\(a^1,a^2,a^3...a^s\)和\(a^{2s},a^{3s},a^{4s}...\)那么类似BSGS可以\(O(1)\)出结果。
预处理复杂度\(\sqrt{p}\)。