By Muhammad_mhs, history, 2 months ago, My approach to solving this problem was the segment tree with O(n(logn)^2) complexity. but It gives me TLE.

My Submission: 124635301

Please, anyone, help me why this solution gives me TLE Comments (26)
 » In my opnion $O(nlog^2n)$ is too slow for this problem. And the constant time complexity is naturally bigger for Segment Tree.Why not try using the Spharse Table? And binary searching the solution of each start i is unnecessary. You can simply use a two-pointer method to get the maximum right segment point of each start i.If you insist your method, then I recommend you use a quicker input method, instead of cin.This is my code.
•  » » 2 months ago, # ^ | ← Rev. 2 →   Total time complexity is $O(nlognlog(max {{a_i}} ))$ for initializing the Spharse Table, and $O(nlog(max {{a_i}} ))$ for getting the answer.
•  » » » You need to note that, for both Sparse Table and Segment Tree, the complexity will have additional factor of $log(MAX)$ because combining function is $gcd(x, y)$.
•  » » » » Ahh,yes. I forgot that.
•  » » I have used ios::sync_with_stdio(0);cin.tie(0); for quicker input method. I have got my mistake. Now, I will try that with the sparse table.Thanks a lot.
•  » » Can you explain the O(NlogN) method? I think the gcd operator will add an additional logN into the total time complexity.
 » Since gcd is built into the segment tree, each range query actually has a complexity of O(logn log1e18), which when combined with the binary search, results in a total time complexity of O(n (log n)^2 log1e18). This ends up being too slow. If you still wish to use a segment tree approach, consider changing the binary search to a 2-pointers approach that reduces it to O(n logn log 1e18), which passes under the time limit.
•  » » Thanks a lot, dear.
•  » » Thanks for the explanation.
•  » » 2 months ago, # ^ | ← Rev. 2 →   No, you are wrong. GCD is in fact $O(log(min(a, b) / ans))$, thus the answering each query with segtree is $O(log(n) + log(max_A))$ which turns out to be good enough for doing binary search. Here's my in contest submission which passed the system tests. $O(n \cdot log(n) \cdot (log(n) + log(max_A)))$: 124574566.
•  » » » It's a very nice observation.
•  » » » That is a very careful observation. Nevertheless, given the large constant factor of a segment tree, it might be best to avoid using binary search, which fails when not using 64-bit.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Can you please elaborate on the GCD complexity?
•  » » » » This should help.
•  » » » » » That was really helpful, thanks :)
 » Can anyone tell how to get rid of Memory Limit Exceeded. I have implemented a segment tree with two pointer approach.My Submission:124646523
•  » » Your query function return int type data. but range gcd can be cross int limit.
•  » » » Actually in my code i have defined int as long long, although it is not a good practice.
•  » » And also there is a corner case that is n = 1. You have to fix this case.
•  » » » Could you share your segment tree accepted solution, it will help a lot.
•  » » » » your code doesn't work for n = 1.My Solution: 124641397
•  » » » » » Thanks for the help, it got accepted. The problem was that i was creating new array for every testcase, just fixed it and also the n==1 corner case.
 » 2 months ago, # | ← Rev. 2 →   The same code passes in 1950ms if you choose language GNU C++17 (64 bit) Link
•  » » Could you please tell me why it doesn't pass GNU C++17?
•  » » » You need to optimize the code, my solution with same logic passes 124697813.
•  » » » » I have used two pointers technique and got AC.