day1 没上200……不应该啊……正常点的话215应该没问题？
题意
给定一个长为 $n (n \le 10^5)$ 的序列，要求支持 2 个操作：
- 把某个区间每个元素 $a_i$ 换成 $c^{a_i}$ ，其中 $c$ 是给定常数。
- 求区间和
思路
PoPoQQQ大爷：这……这不是……上帝和集合的正确用法吗？
然而我做过上帝和集合的正确用法，却没能做出来这题 >.<
有扩展欧拉定理： \(a^b \equiv a^{b \text{ mod }\varphi(n) + [b \ge \varphi(n)]\cdot\varphi(n)} (\text{mod }n)\) 根据上帝和集合的正确用法，这个可以递归下去求，由于 $\varphi(n)$ 每次至少折半，复杂度是 $O(\lg n)$ 级别的。
考试的时候，总是在想：在线段树上面记录什么信息，能够一次执行一个区间的递归求值操作呢？如果只记录加了多少次的话，每次求和就得暴力查，这样复杂度就是每次操作 $O(\lg n) - O(n\lg n)$ 的了……最后也没想出来，交的暴力，发现线性筛求 $\varphi(n)$ 被卡了QAQ
实际上，为什么不换个角度思考呢？与其说一次执行一个区间的递归求值，还不如每次暴力改，在 $O(\lg n)$ 次之后，那个位置原来的值是什么已经无关紧要了，因为递归下去出现了 $\text{mod } 1$ ，最后求出的值一定相同！于是就不用再修改了= =
我们来冷静分析一下复杂度。修改的话区间内每个元素暴力，所有元素最多改 $O(\lg n)$ 次，考虑序列所有元素，最坏复杂度是 $O(n \lg^3 n)$ （每次迭代+快速幂是 $O(\lg^2 n)$ 的），再算上每次在线段树上面分解区间的 $O(\lg n)$ ，总修改复杂度是 $O(n \lg^3 n + q_0 n) = O(n \lg^3 n)$ 的，均摊到每次修改是 $O(\lg^3n)$ 的。每次暴力改的时候维护下区间和，总查询复杂度是 $O(q_1 \lg n)$ 的。
哲♂学分析一下，发现复杂度出现了 $O(\lg n) - O(n\lg n)$ 这种东西，运用根号平衡的思想，也应该想到提高前一半复杂度，降低后一半复杂度？
其实这个思想和维护“区间开方-区间求和”也是类似的……
代码
好像还有一种把快速幂的 $O(\lg n)$ 去掉的方法？
