Suppose we are given an Array A of size N (N<=100000) and each element of array A[i]<=100000. Now I want to find index of rightmost element 'j' in subarray A[1]....A[i-1] for each A[i] such that gcd(A[j],A[i]) is 1 i.e. both are relatively comprime. How can this be done efficiently?
Can you give me Problem link.
a similar problem was given at CEOI 2016, there's an explanation to that problem here http://codeforces.me/blog/entry/46120
I think this problem appeared in a recent contest. Can you provide the link ?