GQR - Need help in removing TLE

help
, , ,
1

Hello guys,
I tried GQR problem and got TLE (as I expected). Here’s a link to my submission.
I am guessing I am getting TLE due to extra log(n) factor in calculating gcd. I read the editorial but couldn’t get it fully. It would be great if someone can help me in understanding that.
Also, is there a way I could improve my solution or is it that I need to change my implementation as per editorial? I mean to ask that if there are any optimizations possible in my solution.

Thanks for the help :slight_smile:

2

It’s O(N^2 log A), it will definitely don’t pass.

Let A[X] is divisible by D, and Y is a position for the previous number(Y<X and A[Y] is divisible by D) for all numbers X and D, so if L <= Y < X <= R then answer is at least D. Think about it.

1 Like
3

Thanks for the response!
Can you explain what does the pre[MAXN] array indicate in your solution?

4

If we’re placing at position i, then pre[d] denotes the maximal position over prefix 1…i-1 such that a[pre[d]] % d == 0.

1 Like
5

Got it finally! Thanks for the help and such a nice problem :slight_smile:

6

@mgch can you please explain how updating only the previous position (instead of all the positions with (a[i] % d == 0)) is working?