Problem link:
PREREQUISITES:
Mobius Function , Maths , MOs Algorithm
PROBLEM:
Given an array A[1...N], and Q queries of the type (L R K), for each query find number of subsets of size K whose GCD = 1.
EXPLANATION:
In order to solve this problem , you must have knowledge about Mobius Function and Mos Algorithm. Read these links for more information: Mobius Function , Mos Algorithm .
Lets discuss the slow solution first.
The answer for a query = Σ_{x= 1}^{100000} ( μ(x) * choose(cnt[x], K) )
where
cnt[x] = number of multiples of x in the subarray A[L…R],
μ(x) = mobius function of x.
Choose(N, R) is number of ways to choose R elements among N different elements.
Read this link if you don’t know how this formula came.
We will be going to consider the numbers which are square free from here on, as μ(x) = 0 for non square free numbers. Any integer will have 2d divisors which are square free, where d = number of distinct prime factors.
Let us also assume that K is fixed in our question. Let us say we know the cnt[] array for the subarray A[L...R], then getting cnt[] array for the subarray A[L…(R+1)] can be done in O(2d) time . Because the cnt[x] will change only if x is a divisor of A[R+1], and there are only 2d square free divisors of A[R+1].
Now we don’t want to run the loop over all x for each query. We use Mo’s Algo here. The speciality of Mo’s algo is that only √N values are added or removed from the subarray A[L...R] before each query. So only O(√N * 2<sup>d</sup>) values of cnt[] array will change.
That means in our answer = Σ_{x= 1}^{100000} ( μ(x) * choose(cnt[x], K) ) , only O(√N * 2d) terms of sum will change. So we have achieved O(Q * √N * 2<sup>d</sup>) solution here, which won’t pass in time yet.
Now let’s define the answer in a different way:
answer for a query = Σ(cntp[y] * choose(y, K)) - Σ (cntn[y] * choose(y, K))
where
cntp[y] = number of x such that cnt[x] = y and μ(x) = 1
cntn[y] = number of x such that cnt[x] = y and μ(x) = -1
Now the tricky part here is to notice that there are at most √N x’s such that cnt[x] >= √N. That means we can store cntp[y], cntn[y] for all y < √N and store the x’s whose cnt[x] >= √N separately in some array or linked list, let’s call this array as Special Array.
Now for each query, update O( √N *2d ) times, the cntp[y], cntn[y] values and the Special Array. As cntp[y] and cntn[y] are just counts, only additions and subtractions are required here. The number of additions after each query will be around O(√N * 2d) (Mo’s Algo).
After all cntp[], cntn[] values are updated, then run a loop over all values of y < √N and Special Array and find the answer using
answer for a query = Σ(cntp[y]-cntn[y]) * choose(y, K) + Σ (μ(x)*choose(cnt[x], K)) for all x’s in Special Array.The number of multiplications here are O(Q*√N).