Playlist (Codeforces 1483B)
Tags: Implement, dsu

Arkady has a playlist that initially consists of $$$n$$$ songs, numerated from $$$1$$$ to $$$n$$$ in the order they appear in the playlist. Arkady starts listening to the songs in the playlist one by one, starting from song $$$1$$$. The playlist is cycled, i. e. after listening to the last song, Arkady will continue listening from the beginning.Each song has a genre $$$a_i$$$, which is a positive integer. Let Arkady finish listening to a song with genre $$$y$$$, and the genre of the next-to-last listened song be $$$x$$$. If $$$\operatorname{gcd}(x, y) = 1$$$, he deletes the last listened song (with genre $$$y$$$) from the playlist. After that he continues listening normally, skipping the deleted songs, and forgetting about songs he listened to before. In other words, after he deletes a song, he can't delete the next song immediately.Here $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.For example, if the initial songs' genres were $$$[5, 9, 2, 10, 15]$$$, then the playlist is converted as follows: [5, 9, 2, 10, 15] $$$\to$$$ [5, 9, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] (because $$$\operatorname{gcd}(5, 9) = 1$$$) $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 10, 15] (because $$$\operatorname{gcd}(5, 2) = 1$$$) $$$\to$$$ [5, 10, 15] $$$\to$$$ [5, 10, 15] $$$\to$$$ ... The bold numbers represent the two last played songs. Note that after a song is deleted, Arkady forgets that he listened to that and the previous songs.Given the initial playlist, please determine which songs are eventually deleted and the order these songs are deleted.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of songs.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the genres of the songs.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single line. First, print a single integer $$$k$$$ — the number of deleted songs. After that print $$$k$$$ distinct integers: deleted songs in the order of their deletion.

Note: Explanation of the first test case is given in the statement.In the second test case, the playlist is converted as follows: [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] (because $$$\operatorname{gcd}(1, 2) = 1$$$) $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [4, 2, 4, 2] (because $$$\operatorname{gcd}(2, 1) = 1$$$) $$$\to$$$ [4, 2, 4, 2] $$$\to$$$ ...In the third test case, the playlist is converted as follows: [1, 2] $$$\to$$$ [1, 2] $$$\to$$$ [1] (because $$$\operatorname{gcd}(1, 2) = 1$$$) $$$\to$$$ [1] $$$\to$$$ [1] (Arkady listened to the same song twice in a row) $$$\to$$$ [] (because $$$\operatorname{gcd}(1, 1) = 1$$$).The fourth test case is same as the third after deletion of the second song.In the fifth test case, the same song is listened to over and over again, but since $$$\operatorname{gcd}(2, 2) \ne 1$$$, it is not deleted.

Sample Inputs:
5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2

Sample Outputs:
2 2 3 
2 2 1 
2 2 1 
1 1 
0

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
    return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
from collections import deque
from math import gcd
from functools import lru_cache

class UnionFind:

    def __init__(self, n):
        self.state = [-1] * n
        self.size_table = [1] * n
        self.cnt = n

    def root(self, u):
        uu = []
        while self.state[u] >= 0:
            uu.append(u)
            u = self.state[u]
        for v in uu:
            self.state[v] = u
        return u

    def merge(self, u, v):
        u = self.root(u)
        v = self.root(v)
        if u == v:
            return
        self.state[u] = v
        self.cnt -= 1
        self.size_table[v] += self.size_table[u]
        return

    def size(self, u):
        return self.size_table[self.root(u)]

@lru_cache(None)
def coprime(a, b):
    return gcd(a, b) == 1
for _ in range(II()):
    n = II()
    aa = LI()
    uf = UnionFind(n)
    q = deque()
    fin = [False] * n
    ans = []
    for i in range(n):
        if fin[i]:
            continue
        j = (i + 1) % n
        if coprime(aa[i], aa[j]):
            fin[j] = True
            ans.append(j + 1)
            uf.merge(j, (j + 1) % n)
            j = uf.root(j)
            if coprime(aa[i], aa[j]):
                q.append((i, j))
    while q:
        (i, j) = q.popleft()
        if fin[i] or fin[j]:
            continue
        fin[j] = True
        ans.append(j + 1)
        uf.merge(j, (j + 1) % n)
        j = uf.root(j)
        if coprime(aa[i], aa[j]):
            q.append((i, j))
    print(len(ans), *ans)

Solution (Python):
from math import gcd
for _ in [*open(0)][2::2]:
    a = (*map(int, _.split()),)
    n = len(a)
    s = []
    f = [*range(1, n)] + [0]
    q = [(i, f[i]) for i in range(n) if gcd(a[i], a[f[i]]) < 2]
    while len(q) != 0:
        (x, y) = q[0]
        q.pop(0)
        if f[x] == y:
            s.append(y + 1)
            f[x] = f[y]
            f[y] = -1
            if f[x] < 0 or x < 0:
                continue
            if gcd(a[x], a[f[x]]) < 2:
                q.append((x, f[x]))
    print(len(s), *s)

Solution (Python):
from math import gcd
for _ in [*open(0)][2::2]:
    a = (*map(int, _.split()),)
    n = len(a)
    s = []
    f = [*range(1, n)] + [0]
    q = [(i, f[i]) for i in range(n) if gcd(a[i], a[f[i]]) < 2]
    while len(q) != 0:
        (x, y) = q[0]
        q.pop(0)
        if f[x] == y:
            s.append(y + 1)
            f[x] = f[y]
            f[y] = -1
            if f[x] < 0 or x < 0:
                continue
            if gcd(a[x], a[f[x]]) < 2:
                q.append((x, f[x]))
    print(len(s), *s)