题目解析

本题要求维护一个长度为 ( n ) 的数组，支持两种操作：

• 修改操作（0 l r）：将区间 ([l, r]) 内的每个元素 ( a_i ) 替换为 ( c^{a_i} )，即 ( c ) 的 ( a_i ) 次方。
• 查询操作（1 l r）：求区间 ([l, r]) 内所有元素的和，输出结果对 ( p ) 取模的值。

直接计算指数幂不可行，因为 ( c ) 和 ( a_i ) 可能很大，且多次修改后值会急剧增长。解决方案基于数论中的欧拉定理：对于互质的 ( a ) 和 ( n )，有 [ a^{\phi(n)} \equiv 1 \pmod{n} ] 其中 ( \phi(n) ) 是欧拉函数。对于非互质情况，有扩展形式：当指数足够大时， [ a^b \equiv a^{b \mod \phi(n) + \phi(n)} \pmod{n} ]

关键思路：

1. 欧拉函数链：迭代计算 [ p_0 = p,\quad p_1 = \phi(p),\quad p_2 = \phi(\phi(p)),\quad \dots ] 直到 ( p_m = 1 )。由于欧拉函数值快速下降，链长 ( m ) 为 ( O(\log p) ) 级别。

2. 幂塔计算：对于 ( k ) 层指数塔 [ c^{c^{\cdots^{c^{a_i}}}} \pmod{p} ] 通过递归从顶层到底层利用欧拉定理计算。递归函数 ( F(k, a, \phi_i) ) 计算 ( k ) 层指数塔模 ( \phi_i ) 的值，返回时确保指数大小信息（通过返回模值加上 ( \phi_i ) 若值足够大）。

3. 预处理：

   • 预计算欧拉链 ( \phi[1 \dots m] )。
   • 预计算幂表 ( \text{power}[0][i][x] ) 和 ( \text{power}[1][i][x] ) 用于快速计算 ( c^x \mod \phi[i] )（采用分块方法）。
   • 对于每个初始值 ( a_i )，预计算其经过 ( j ) 次修改后的值 ( a[i][j] )（( j ) 从 0 到 ( m-1 )），因为修改次数超过 ( m-1 ) 后值不再变化。

4. 线段树维护：

   • 线段树节点存储区间和与区间最小修改次数。
   • 修改操作：区间内每个位置修改次数加 1（不超过 ( m-1 )），并更新为预计算的值。
   • 查询操作：返回区间和模 ( p )。

这种方法将问题转化为利用欧拉定理处理指数塔，并通过预处理和线段树高效支持区间操作。