Previous Coprime Element

4.7

3 votes
Inclusion-exclusion, Data Structures, Segment Trees, Advanced Data Structures, Basic Programming, Number theory, Combinatorics, Math
Problem

Given an Array \(arr\) of length \(N\) find the index (0-indexed) of previous co-prime element for each index \(0 \le i < N\), or \(-1\) if there's no such value.

Two values \(x\) and \(y\) are called co-prime if \(GCD(x, y) = 1\).

Previous co-prime element of \(arr[i]\) is the first element co-prime to \(arr[i]\) on the left of index \(i\), ie. maximum \(j\) such that \(GCD(arr[i], arr[j]) = 1\) and \(j < i\), or -1 if there's no co-prime element to the left of \(arr[i]\).

NOTE:

  • Use of Fast I/O is recommended for this problem.

Input Format:

  • First line contains an integer \(T\) denoting the number of test cases.
  • First line of each testcase contains an integer \(N\) denoting length of \(arr\).
  • Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).

Output Format:

  • For each testcase, In a single line, print the index of previous co-prime element of \(arr[i]\) for each index \(0 \le i < N\), or \(-1\) if no such value.

Constraints:

  • \(1 \le T \le 10\)
  • \(1 \le N \le 10^5\)
  • \(1 \le arr[i] \le 10^5\)
Time Limit: 6
Memory Limit: 512
Source Limit:
Explanation

In third testcase, \(arr = [3, 6, 9, 1, 2, 3]\)

First, Second and Third element has no co-prime element to left, hence \(-1\) is their previous index.

Fourth element is co-prime to \(9\), ie. index \(2\).

Fifth element is co-prime to \(1\), ie. index \(3\).

Sixth element is co-prime to \(2\), ie. index \(4\).

Editor Image

?