Playlist Codeforces Round #709 Div. 2 Solution

Playlist solution codeforces

Arkady has a playlist that initially consists of nn songs, numerated from 11 to nn in the order they appear in the playlist. Arkady starts listening to the songs in the playlist one by one, starting from song 11. The playlist is cycled, i. e. after listening to the last song, Arkady will continue listening from the beginning.

Each song has a genre aiai, which is a positive integer. Let Arkady finish listening to a song with genre yy, and the genre of the next-to-last listened song be xx. If gcd(x,y)=1gcd⁡(x,y)=1, he deletes the last listened song (with genre yy) 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. Playlist solution codeforces

Here gcd(x,y)gcd⁡(x,y) denotes the greatest common divisor (GCD) of integers xx and yy.

For example, if the initial songs’ genres were [5,9,2,10,15][5,9,2,10,15], then the playlist is converted as follows: [5, 9, 2, 10, 15] →→ [5, 9, 2, 10, 15] →→ [5, 2, 10, 15] (because gcd(5,9)=1gcd⁡(5,9)=1) →→ [5, 2, 10, 15] →→ [5, 2, 10, 15] →→ [5, 2, 10, 15] →→ [5, 2, 10, 15] →→ [5, 2, 10, 15] →→ [5, 10, 15] (because gcd(5,2)=1gcd⁡(5,2)=1) →→ [5, 10, 15] →→ [5, 10, 15] →→ … 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 Playlist solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤100001≤t≤10000). Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105) — the number of songs.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the genres of the songs.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.Output Playlist solution codeforces

For each test case, print a single line. First, print a single integer kk — the number of deleted songs. After that print kk distinct integers: deleted songs in the order of their deletion.Exampleinput Playlist solution codeforcesCopy

5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2

outputCopy

2 2 3 
2 2 1 
2 2 1 
1 1 
0 

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] →→ [1, 2, 4, 2, 4, 2] →→ [1, 4, 2, 4, 2] (because gcd(1,2)=1gcd⁡(1,2)=1) →→ [1, 4, 2, 4, 2] →→ [1, 4, 2, 4, 2] →→ [1, 4, 2, 4, 2] →→ [1, 4, 2, 4, 2] →→ [1, 4, 2, 4, 2] →→ [4, 2, 4, 2] (because gcd(2,1)=1gcd⁡(2,1)=1) →→ [4, 2, 4, 2] →→ …

In the third test case, the playlist is converted as follows: [1, 2] →→ [1, 2] →→ [1] (because gcd(1,2)=1gcd⁡(1,2)=1) →→ [1] →→ [1] (Arkady listened to the same song twice in a row) →→ [] (because gcd(1,1)=1gcd⁡(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 gcd(2,2)≠1gcd⁡(2,2)≠1, it is not deleted.

Leave a Comment