P16852 [GKS 2021 #D] Primes and Queries

给定一个素数 $P$。 定义 $V(x)$ 为 $x$ 的质因数分解中 $P$ 的次数。更明确地说，若 $V(x) = y$，则 $x$ 能被 $P^y$ 整除，但不能被 $P^{y+1}$ 整除。 此外，定义 $V(0) = 0$。 例如，当 $P = 3$ 且 $x = 45$ 时，由于 $45 = 5 \cdot 3^2$，因此 $V(45) = 2$。 你还得到一个包含 $N$ 个元素的数组 $A$。你需要处理 $Q$ 个查询，查询有两种类型： - 类型 $1$ 查询：`1 pos val` – 将位置 $pos$ 上的元素赋值为 $val$，即 $A_{pos} := val$。 - 类型 $2$ 查询：`2 S L R` – 输出 $\sum_{i=L}^{R} V(A_i^S - (A_i \bmod P)^S)$。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含三个空格分隔的正整数 $N$、$Q$ 和 $P$，分别表示数组的元素个数、查询的数量以及一个素数。 下一行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$，表示数组 $A$ 的元素。 接下来的 $Q$ 行每行描述一个查询，每行要么包含三个空格分隔的正整数：`1 pos val`，要么包含四个空格分隔的正整数：`2 S L R`。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是按顺序排列的每个类型 $2$ 查询的答案列表。

在样例 #1 中： 第一个查询是类型 $2$ 查询，其中 $S = 3$，$L = 3$，$R = 4$。让我们计算该查询的结果： $$ \begin{aligned} i &= 3,\ V(62^3 - (62 \bmod 2)^3) = 3 \\ i &= 4,\ V(67^3 - (67 \bmod 2)^3) = 1 \\ &\sum_{i=3}^{4} V(A_i^3 - (A_i \bmod P)^3) = 3 + 1 = 4 \end{aligned} $$ 第二个查询是类型 $1$ 查询，我们需要将 $69$ 赋给 $A_1$，因此数组 $A$ 变为：$69\ 94\ 62\ 67\ 91$。 ### 限制条件 $1 \le T \le 100$ $2 \le P \le 10^9$ $P$ 是素数。 $1 \le pos \le N$ $1 \le L \le R \le N$ 最多 $10$ 个测试用例满足： $1 \le N \le 5 \times 10^5$ $1 \le Q \le 10^5$ 其余测试用例满足： $1 \le N \le 10^3$ $1 \le Q \le 10^3$ 保证至少存在一个类型 $2$ 查询。 **测试集 1** $1 \le S \le 4$ $1 \le A_i \le 10^3$ $1 \le val \le 10^3$ **测试集 2** $1 \le S \le 10^9$ $1 \le A_i \le 10^{18}$ $1 \le val \le 10^{18}$ 翻译由 DeepSeek V4 Pro 完成