Задача №114304. Расстояние
Рассмотрим следующую операцию, определённую на целых положительных числах. Операция состоит в умножении числа \(q\) на простое число \(p\), либо в делении числа \(q\) на простое число \(p\), если \(q\) делится на \(p\) без остатка. Назовем расстоянием между числами \(a\) и \(b\) минимальное количество операций, необходимое для того чтобы получить из числа \(a\) число \(b\). Обозначим расстояние как \(d(a, b)\).
Дана последовательность из \(n\) положительных чисел \(a_1, a_2, ... a_n\). Для каждого индекса \(i\) (\( 1 \le i \le n\)) необходимо найти индекс \(j\), такой что \(1 \le j \le n\) и \(i \ne j\), и что \(d(a_i, a_j)\) минимально.
Первая строка входных данных содержит одно целое число \(n\) — количество элементов в последовательности \(a\) (\(1 \le n \le 100 000\)).
В последующих \(n\) строках входных данных даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — элементы последовательности (\(1 \le a_i \le 10^{6}\)) (\(i\)-е число в \(i + 1\) строке).
Выведете \(n\) строк. В \(i\) строке выведете такой минимальный индекс \(j\), такой что \(1 \le j \le n\) и \(i \ne j\), и что \(d(a_i, a_j)\) минимально.
В тестах суммарной стоимостью не менее \(30\) баллов дополнительно гарантируется что \(n \le 1000\), \(a_i \le 10000\).
6 1 2 3 4 5 6
2 1 1 2 1 2
2 1 1
2 1