P16852 [GKS 2021 #D] Primes and Queries

You are given a prime number $P$. Let's define $V(x)$ as the degree of $P$ in the prime factorization of $x$. To be clearer, if $V(x) = y$ then $x$ is divisible by $P^y$, but not divisible by $P^{y+1}$. Also we define $V(0) = 0$. For example, when $P = 3$, and $x = 45$, since $45 = 5 \cdot 3^2$, therefore $V(45) = 2$. You are also given an array $A$ with $N$ elements. You need to process $Q$ queries of $2$ types on this array: - type $1$ query: $1$ $pos$ $val$ - assign a value $val$ to the element at $pos$, i.e. $A_{pos} := val$ - type $2$ query: $2$ $S$ $L$ $R$ - print $\sum_{i=L}^{R} V(A_i^S - (A_i \bmod P)^S)$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains $3$ space separated positive integers $N$, $Q$ and $P$ - the number of elements in the array, the number of queries and a prime number. The next line contains $N$ positive integers $A_1, A_2, \ldots, A_N$ representing elements of array $A$. Each of the next $Q$ lines describes a query, and contains either - $3$ space separated positive integers: $1$ $pos$ $val$ - or $4$ space separated positive integers: $2$ $S$ $L$ $R$

For each test case, output one line containing `Case #`$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is a list of the answers for each query of type $2$.

In Sample Case #$1$ The first query is a query of type $2$, where $S = 3$, $L = 3$, $R = 4$. Let's calculate the result for this query: $$ \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} $$ The second query is of type $1$, where we need to assign $69$ to $A_1$, so our array $A$ now becomes: $69\ 94\ 62\ 67\ 91$. ### Limits $1 \le T \le 100$ $2 \le P \le 10^9$ $P$ is a prime number. $1 \le pos \le N$ $1 \le L \le R \le N$ For at most $10$ cases: $1 \le N \le 5 \times 10^5$ $1 \le Q \le 10^5$ For the remaining test cases: $1 \le N \le 10^3$ $1 \le Q \le 10^3$ There will always be at least one query of type $2$. **Test Set $1$** $1 \le S \le 4$ $1 \le A_i \le 10^3$ $1 \le val \le 10^3$ **Test Set $2$** $1 \le S \le 10^9$ $1 \le A_i \le 10^{18}$ $1 \le val \le 10^{18}$