Problem Link
Author : Himanshu Jaju
Editorialist : Himanshu Jaju
Difficulty
Medium
PREREQUISITES:
Bitset, Segment Tree, Basic Maths
Explaination
Let us try to solve a simpler version of this question first : “Given N prime numbers, find gcd(X, phi(X)) modulo 10^9 + 7, where X = product of all distinct primes among the N given numbers.”
The first thing to observe is that the gcd obtained will also be a product of distinct primes. So we just need to know whether a prime factor of X exists in phi(X) or not. We can see that bitset is a useful structure to use to reduct time and memory consumption. Also, note that phi(N) is a multiplicative function and hence it can be calculated independently for each prime and then merged.
Now, we have two bitsets : one for X and one for phi(X). Taking bitwise AND of these two bitsets gives us our gcd bitset. In this process, we have solved our simplified version.
To solve the original problem, you can create a segment tree with bitsets at every node. The merge operation is a simple bitwise OR operation. Both the queries can now be answered in O(logN * PI(10^5) / 32), where PI(N) is the number of primes lesser or equal to N. Thus, we can solve the problem now in O(Q * logN * PI(10^5) / 32) which is ~ 8 * 10^7 operations.