Last Updated: 5 Jul, 2021
Co-prime Twins
Hard
Asked in companies
A pair of positive integers (a, b) is said to be a coprime-twin pair, if for all positive integers x, both a and b and are coprime to x or both and are not coprime to x. Formally, 2 distinct positive integers a and b can form a coprime-twin pair if and only if S(a) = S(b), where S(x) denotes the set of all positive integers that are coprime to x.
For example:
2 and 4 are coprime-twin pairs.
1 and 2 are not coprime-twin pairs.
The score of a sequence a1, a2, .. an is the number of indices (i, j) such that i < j and the pair (ai, aj) forms a coprime-twin pair.
You are given an array A of positive integers and Q queries of the form L, R. For each query, determine the score of the subarray [L, R] inclusive.
Note: A subarray is a contiguous non-empty segment of the array.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers N and Q which denote the number of elements in the array A and the number of queries you need to answer respectively.
The next line contains N space-separated integers denoting the array a1, a2, … an.
The next Q lines contain two integers each - Li and Ri, the parameters of the ith query.
Output Format:
For each test case, Q lines
For each of the next Q lines, print a single integer denoting the answer for the ith query.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N, Q <= 10^4
1 <= Ai <= 10^6
1 <= L <= R <= N
Time Limit: 1 sec.
Approaches
Two numbers are called co-prime twins if and only if the set of primes in its prime factorization is equal.
So for any number, we need to reduce any power of a prime to only single if we want to compare the sets.
If x = p1^x1*p2^x2 … pk^xk
we can reduce it to
x = p1 * p2 * p, .. pk
Now, this can be done using pre-computation of primes using a sieve of Eratosthenes.
Now we just need to count for each query the number of equal pairs in that range which can be done using a count array..
Algorithm:
coprimeTwins (Q, A) returns the answer for each of the queries in Q.
- Call pre-computation function to calculate the reduced form of each number from 1 to MAX.
- Replace each of the array elements to its reduced form.
- Now for each query L, R iterate from L to R and increase the answer by cnt[arr[i]] and increase it by 1.
- Finally, reset the cnt array to zero again.
precompute(reduced) returns an array where each index stores its reduced form.
- We run a sieve from 1 to MAX and if reduced[i] == 1 (it is a prime) then we iterate over all its multiples and multiply reduced[j] by i.
We will use the idea of approach 1 to reduce the numbers to only one power of each prime. After that instead of answering each query at the time of input, we take all the queries at once and try to answer them in Mo’s algorithm order.
Suppose we want to extend the interval from [L, R] to [L, R + 1] we increase the count of answers by cnt[arr[R + 1]] because that many numbers of new pairs will be added. We follow a similar algorithm to shrink the interval.
Algorithm:
coprimeTwins (Q, A) returns the answer for each of the queries in Q.
- Call pre-computation function to calculate the reduced form of each number from 1 to MAX.
- Replace each of the array elements to its reduced form.
- Sort all the queries according to Mo’s algorithm.
- Iterate over all the queries from 1 to Q and expand and shrink the interval by calling the add and remove functions.
- Store the answer for each query in the answer array.
- Return the answer array.
precompute(reduced) returns an array where each index stores its reduced form.
- We run a sieve from 1 to MAX and if reduced[i] == 1 (it is a prime) then we iterate over all its multiples and multiply reduced[j] by i.