×

# GCDCNT - Editorial

Author: Vipul Sharma
Tester: Triveni Mahatha

Medium

# PREREQUISITES:

Inclusion exclusion, Ordered Set

# PROBLEM:

You are given an array with $N$ elements. You need to support two types of operations on this array. First one is point update. For the second operation, you will be given query range $l,r$ and an another number $G$ as input, you need to find number of elements that are co-prime to $G$ in the given range.

# EXPLANATION:

Let's try to find the number of integers co-prime to $G$ in the given query range, represented by $ANS(G,L,R)$. Say,

$G = p_1^{a_1} . p_2^{a_2} . ..... p_q^{a_q}$

We will be using inclusion-exclusion principle to find the required expression. Lets represent number of integers divisible by $x$ from the range $L,R$ as $F(x,L,R)$. Then, we can write:

$$ANS(G,L,R) = F(1,L,R) - \sum \limits_{i=1}^q F(p_i,L,R) \\ + \sum \limits_{i=1}^q \sum \limits_{j=i+1}^q F(p_i.p_j,L,R) \\ - (\text{3 at a time}) \\ + (\text{4 at a time}) \\ - ... + (-1)^q.F(\prod \limits_{i=1}^q p_i,L,R)$$

Number of terms in expansion of $ANS(G,L,R)$ is $2^q$, where $q$ is number of distinct prime factors of $G$. Also, notice that first argument to function $F$ is always a square free divisor of $G$. If we can answer $F(x,L,R)$ in logarithmic complexity, we can have a solution that will work in $O(2^q.logN)$ for each query.

We will maintain an ordered set for each of the number $1 \le x \le 10^5$. For all $A[i]$ $(1 \le i \le N)$, we will iterate over its square free divisors and insert this index $i$ in the ordered set of corresponding divisors. Since, a number upto $10^5$ can have at-max 64 square free divisors, this will take a time of $O(K.N.logN)$ where $K=64$. You can answer $F(x,L,R)$ in $O(logN)$ time by querying over ordered set corresponding to $x$. We can also support the update in similar fashion. Say, current update operation is to change $A[x]$ to $y$. First, we will iterate over square free divisors of $A[x]$ and erase index $x$ from the ordered set of corresponding divisors. Then, we will iterate over square free divisors of $y$ and insert index $x$ into the ordered set of corresponding divisors. Finally, make $A[x]=y$.

# ALTERNATE SOLUTION

This solution requires knowledge of mobius inversion. You can refer to some of these awesome links(L1, L2), in case you are not familiar with the same. Lets represent unit function by $e(n)$. Then, we can write:

Question tags:

×15,006
×2,474
×264
×44
×24
×20