시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
90 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 13 | 7 | 6 | 50.000% |
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:
1 pos val
- assign a value $val$ to the element at $pos$, i.e. $A_{pos} := val$2 S L R
- print $\displaystyle\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$, $\cdots$, $A_N$ representing elements of array $A$.
Each of the next $Q$ lines describes a query, and contains either
1 pos val
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$.
For at most 10 cases:
For the remaining test cases:
There will always be at least one query of type $2$.
2 5 5 2 16 94 62 67 91 2 3 3 4 1 1 69 2 3 1 4 2 1 1 1 2 3 2 2 5 5 5 1 2 3 4 5 2 1 1 5 1 3 98 2 3 2 4 1 5 3 2 2 1 5
Case #1: 4 9 2 3 Case #2: 1 1 1
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:
$i=3$, $V(62^3 - (62 \bmod 2)^3)=3$
$i=4$, $V(67^3 - (67 \bmod 2)^3)=1$
$\displaystyle\sum_{i=3}^{4}{V(A_i^3 - (A_i \bmod P)^3)} = 3+1 = 4$
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
.
Contest > Google > Kick Start > Google Kick Start 2021 > Round D D번