Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Ryo and his girlfriend love to think about challenges. One day his girlfriend gave him a challenge to solve a problem. She gave him a function named RivalryFriends.

The function counts the number of integers between 1 and n inclusive, which are relatively prime to n, i.e. the numbers whose highest common factor with n is 1. `RivalryFriends(1)`

is defined to be 1. Examples:

```
RivalryFriends(5) = 4
RivalryFriends(6) = 2
```

Here, {1, 2, 3, 4} are relatively prime to 5. So `RivalryFriends(5) = 4`

.

Similarly, {1, 5} are relatively prime to 6. Hence `RivalryFriends(6) = 2`

.

Now, Ryo has to calculate the function, RivalryFriends for any n. As Ryo is very talented, he easily solved the problem. So Ryo and his girlfriend thought of making a new problem with a twist for you. Now you will be given an integer array A[] of size n and q queries to perform on the array. The queries will be:

Query type 1: Set the value of the i'th element to v, i.e. A[i] = v. This type of query appears in the input in 1 i v format.

Query type 2: Print the value of the function given below:

$\sum\limits_{i=l}^{r}{RivalryFriends(A[i])}$

This second type of query appears in the input in `2 l r`

format.

The first line of input contains two integers **n** (1 ≤ n ≤ 105) and **q** (1 ≤ q ≤ 105).

The next line will contain n space separated integers in the range [1, 105].

Each of the next q lines contains a task in one of the following form:

`1 i v`

: Set the value of **ith** (1 ≤ i ≤ n) element to **v** (1 ≤ v ≤ 105).

`2 l r`

: Print the value of the function. (1 ≤ l ≤ r ≤ n)

For each query of type 2, print the value of the function.

Input | Output |
---|---|

3 3 1 2 3 2 1 3 1 3 5 2 1 3 | 4 6 |

90% Solution Ratio

Gias_UddinEarliest,

RamprosadGFastest, 0.0s

sagar1230Lightest, 2.0 MB

Ruffian_SalehShortest, 887B

Login to submit

Category: Number theory and Segment tree.

Toph uses cookies. By continuing you agree to our Cookie Policy.