Codeforces Round 323 (Div. 1) |
---|
Закончено |
Таблица НОД G размера n × n для массива целых положительных чисел a длины n задается формулой
Напомним, что наибольшим общим делителем (НОД) двух положительных целых чисел x и y называется наибольшее целое число, делящее одновременно и x и y, оно обозначается как . Например, для массива a = {4, 3, 6, 2} длины 4 таблица НОД будет выглядеть следующим образом:
Зная все числа таблицы НОД G, восстановите массив a.
В первой строке содержится число n (1 ≤ n ≤ 500) - длина массива a. Во второй строке содержатся n2 чисел, разделенных пробелом - элементы таблицы НОД G для массива a. Все числа таблицы целые положительные и не превышают 109. Обратите внимание, что элементы заданы в произвольном порядке. Гарантируется, что набору входных данных соответствует некоторый массив a.
В единственную строку выведите n целых положительных чисел - элементы массива a. Если возможных решений несколько, разрешается вывести любое.
4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2
4 3 6 2
1
42
42
2
1 1 1 1
1 1
Название |
---|