GCD and Sum

upobir Criterion 2021 Round 12
Limits 1.5s, 512 MB

Congratulations! You’ve been hired in “Buggy Software Ltd.” And you’ve been already given your first assignment. Initially, you’ll be given a nn length array aa of numbers. Then you’ll be given qq queries of two types:

  1. 1 l r: meaning that calculate the sum of elements whose indices ii satisfy lirl \leq i \leq r
  2. 2 l r g: meaning that change all aia_i to aigcd(ai,g)\frac{a_i}{\gcd(a_i, g)}where lirl \leq i \leq r

You have to print the results of the queries of the first type.


The first line will contain two integers nn and qq, the size of aa and number of queries respectively. The next line will contain nn space separated integers, the contents of array aa. Next qq lines will each contain the queries: 1 l r or 2 l r g.

1n21051 \leq n \leq 2\cdot 10^5

1q21051 \leq q \leq 2\cdot 10^5

1ai21051 \leq a_i \leq 2\cdot 10^5

1lrn1 \leq l \leq r \leq n

1g21051 \leq g \leq 2\cdot 10^5


For each query of type 1, output the answer in a single line.


5 4
2 4 6 8 10
1 2 5
2 1 3 2
2 3 5 3
1 1 5


Login to submit.


44% Solution Ratio
solaimanopeEarliest, Apr '21
rkb_rdFastest, 0.2s
rkb_rdLightest, 49 MB
mahade31Shortest, 1534B
Toph uses cookies. By continuing you agree to our Cookie Policy.