Luogu分析这种题显然要用扩展欧拉定理先考虑没有修改的情况,我们只需要像其它扩展欧拉定理题一样递归下去即可。显然只会递归 $\mathcal{O}(\log p)$ 层,所以复杂度是对的。现在考虑这个修改。我们实际上只需要知道每个位置的值,因此用树状数组实现区间修改、单点查询即可。$\varphi(p)$ 的值显然不能在递归时 $\mathcal{O}(\sqrt{p})$ 求,但是 $p...
LuoguLOJ分析扩展欧拉定理:可以发现 $c^{c^{c^{c^\cdots}}}$ 至多 $\log$ 层后指数的模数就会变成 $1$ ,于是可以 $O(\log n)$ 计算这个东西。于是修改直接暴力修改到叶子节点,如果修改次数已经超过最大值了就不用改直接返回。具体的,稍微修改一下快速幂,使得它能够判断扩展欧拉定理的条件,然后返回对应的值。这样子时间复杂度是 $O(n\log^3n)...