But, there are 2e7 queries in the worst case and answering each in log n time would take (2e7 * log n) computations which was failing clearly in C++. Not sure how it passed in python.
I dont know if ‘range product queries’ can be answered in O(1) per query using Sparse Table. In that case it would pass.
i don’t have much experience in c++, but i guess % is taking your time. % take same time as division takes, which is O(N^2) , N being number of digits. May be that’s what causing TLE. Replace value%N with
if(value>=N)value%=N
Hopefully all tle turn into AC.
Or you may try iterative version of gcd Extended.
I tried the iterative version also.
I think i should try that modulus part.
Thanks ,any more optimisations can be done?
I am amazed too.
@taran_1407 I have asked a question for SEGPROD. It will be really helpful if you could help me debug my code and telling me where I am wrong.
I hope that would suffice. Else see fast solutions of other coders. (not mine though, it just passed on borderline 
)
Thanx a lot!!
I did around 120 submissions and couldnt figure this thing.
Will always keep this in mind.
@jaideeppyne Yes, my solution is O(NLogN + QLogN). But I’ve submitted it in PYPY, it’s time limit is same as that of Python i.e. 5x that of C++. However, PYPY is significantly faster than Python. So, in the end, my solution passed just within the time limits.
Exactly what I did, except that I used 2 segment trees one for elements >= L and one for elements > R.
No need for square root decomposition to get 52 points (CSUBQ). 
Thanks to both of u for sharing ur approach…
Though ur approach was nice, But to tell the truth, this is my first ever segtree non classical problem which i managed to solve. 2 segtree would be too much for first timers…
That’s great
Great.
Often when queries are 10^7, pre calculation is vital
I would not always say to avoid recursive ones, but constraints were too tight for this problem. Iterative is a little bit faster, for ur power left function.
U may try making it iterative.
Try using arrays in place of vectors…
Hopefully that works because arrays tend to be faster than vectors.
Mate, ur complexity may be QlogN, but in some problems, u also have to take care of constant factor associated, which i believe, is the reason of tle.
@codent47 Always consider using iteration instead of recursion wherever possible. Infact you can do that for all your three power functions, I am pretty sure, it would pass then. And also consider using Fast I/Os in such questions where TL is too strict.
Also try using arrays instead of vectors, vectors are a bit slower than arrays.
Honestly, I feel that setter and tester were extremely wrong in setting the time limit. I wonder how much time setter’s code takes to run, cause if its something like 3.8-3.9seconds, then time limit is wrongly put.
Saying because, languages like java etc. got accepted (time bonus), while c++ got tle.
Nice use of binary search. 
@eugait