Big Vova (Codeforces 1407B)
Tags: Greedy, number theory

Alexander is a well-known programmer. Today he decided to finally go out and play football, but with the first hit he left a dent on the new Rolls-Royce of the wealthy businessman Big Vova. Vladimir has recently opened a store on the popular online marketplace "Zmey-Gorynych", and offers Alex a job: if he shows his programming skills by solving a task, he'll work as a cybersecurity specialist. Otherwise, he'll be delivering some doubtful products for the next two years.You're given $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$. Using each of them exactly at once, you're to make such sequence $$$b_1, b_2, \dots, b_n$$$ that sequence $$$c_1, c_2, \dots, c_n$$$ is lexicographically maximal, where $$$c_i=GCD(b_1,\dots,b_i)$$$ - the greatest common divisor of the first $$$i$$$ elements of $$$b$$$. Alexander is really afraid of the conditions of this simple task, so he asks you to solve it.A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if and only if one of the following holds: $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$; in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

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

Output: For each test case output the answer in a single line  — the desired sequence $$$b$$$. If there are multiple answers, print any.

Note: In the first test case of the example, there are only two possible permutations $$$b$$$  — $$$[2, 5]$$$ and $$$[5, 2]$$$: for the first one $$$c=[2, 1]$$$, for the second one $$$c=[5, 1]$$$.In the third test case of the example, number $$$9$$$ should be the first in $$$b$$$, and $$$GCD(9, 3)=3$$$, $$$GCD(9, 8)=1$$$, so the second number of $$$b$$$ should be $$$3$$$.In the seventh test case of the example, first four numbers pairwise have a common divisor (a power of two), but none of them can be the first in the optimal permutation $$$b$$$.

Sample Inputs:
7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17

Sample Outputs:
5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
tc = int(input())
for _ in range(tc):
    n = int(input())
    ls = list(map(int, input().split()))
    visited = [0] * n
    res = []
    ls = sorted(ls, reverse=True)
    res.append(ls[0])
    visited[0] = 1
    flag = 1
    currgcd = ls[0]
    for i in range(1, n):
        maxgcd = 0
        ind = -1
        for j in range(n):
            if visited[j] == 0:
                gc = gcd(currgcd, ls[j])
                if maxgcd < gc:
                    maxgcd = gc
                    ind = j
        if maxgcd == 1:
            flag = 0
            break
        currgcd = maxgcd
        res.append(ls[ind])
        visited[ind] = 1
    if flag == 0:
        for i in range(n):
            if visited[i] == 0:
                res.append(ls[i])
    for i in res:
        print(i, end=' ')
    print('')

Solution (Python):
from collections import defaultdict
import math

def main():
    n = int(input())
    l = list(map(int, input().split()))
    maxi = max(l)
    l.remove(maxi)
    l2 = [maxi]
    gcd = maxi
    while l != []:
        lst = []
        maxi = 0
        for i in range(len(l)):
            if math.gcd(gcd, l[i]) > maxi:
                maxi = math.gcd(gcd, l[i])
                lst = [i]
            elif math.gcd(gcd, l[i]) == maxi:
                lst.append(i)
        gcd = maxi
        lst = sorted(lst, reverse=True)
        for ele in lst:
            l2.append(l[ele])
            l.pop(ele)
    for ele in l2:
        print(ele, end=' ')
    print()
for i in range(int(input())):
    main()

Solution (Python):
import math
I = lambda : map(int, input().split())
for _ in [0] * int(input()):
    n = int(input())
    a = list(I())
    x = curgcd = max(a)
    a.remove(x)
    b = [x] + [0] * (n - 1)
    for i in range(1, n):
        k = ind = uear = 0
        for y in a:
            u = math.gcd(y, curgcd)
            if u > uear:
                uear = u
                num = y
                ind = k
            k = k + 1
        b[i] = num
        del a[ind]
        curgcd = uear
        if uear == 1:
            b = b[:i + 1] + a
            break
    print(*b)