Very hard problem. In order to pass all test cases you have to build a segment tree, but only for those L less than 200000. L larger than 1000000 requires a different approach. For segment tree the complexity is O(T * logL^2) where L is the largest L <= 200000.

Nice problem. Learnt a lot about segment tree and use of sieve and recursive approach to pass all test cases. Thanks a lot.

Have been working on the second constraint. My strategy was to first sort the input , and sort the radicals in place according to the increasing . With Python, I couldn't work around the in-place sorting quickly enough (thought of insertion sort, but without pointer it's hopeless).

Then I tried to use the radicals as hash keys, so we won't have to go through the smaller integers again and again (sorting is, after all, at best, which is a lot when we need to do this for every ). But with this kind of hashing, getting the target element is no longer , as we would have to iterate all the hash keys before we hit our target (that makes it I believe). Still not passing it on time.

By the way, I was generating all radicals till aiming for the first two constraints. I think we need to take another approach (iterating on radical and count its occurrences within the upper limit) for the last.

Dang, this one was tough. Anyone able to do this with a single approach? I had to split it into two: one for large L (e.g. L > 1000000), and one for small (<= 1000000).

is there a way to get test cases??.I have done some optimizations,but it does not seems to run.Any one able to solve it succesfully.