abhikolar1512's blog

Coprime pairs.
By abhikolar1512, history, 7 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Can you give me Problem link.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a similar problem was given at CEOI 2016, there's an explanation to that problem here http://mirror.codeforces.com/blog/entry/46120

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this problem appeared in a recent contest. Can you provide the link ?

→ Reply