how to find F(x,L,R) in O(logN) time by querying over ordered set corresponding to x ? If I am using ordered_map , I can get iterator corresponding to L and R in O(logN) . But getting their difference will take linear time .
I have used the fact that any number <=1e5 can have at most 6 prime divisors.
I have found out all prime numbers <=1e5 (~10000) using sieve, used a Java BitSet array to mask each prime number. Each array element has its respective array index position marked in their respective prime divisor BitSet.
For example, if the 3rd element has prime factors (2, 5 & 13), the 3rd index of the BitSet at index (0, 2, 5) are marked true [1st prime = 2, 6th prime = 13].
For update it takes at most 12 operations - unmark existing marked positions (6 operations), mark new positions (another 6). The prime factor decomposition takes hardly log n time.
For query operation, the input ‘g’ is prime factorised (log n time operation), and the corresponding BitSets are 'or’ed. From the resulting BitSet the required range is extracted and then some easy calculations follow…
To be honest, I did not expect Java BitSet to be so efficient and fast. I tried segment trees with BitSet, but got TLE. Suddenly this algo clicked in my mind and I got an AC in a single shot… 
My solution: https://www.codechef.com/viewsolution/17593545
4 Likes
@sarthakmanna: I think that number of different divisors is actually 6, for number: 30030 = 235711*13
nice approach sir +1