|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||128 MB||134||29||17||23.944%|
We consider the distance between positive integers in this problem, defined as follows. A single operation consists in either multiplying a given number by a prime number1 or dividing it by a prime number (if it does divide without a remainder). The distance between the numbers a and b, denoted d(a,b), is the minimum number of operations it takes to transform the number a into the number b. For example, d(69,42)=3.
Observe that the function d is indeed a distance function - for any positive integers a,b, and c the following hold:
A sequence of n positive integers, a1,a2,…,an, is given. For each number ai we have to determine j such that j≠i and d(ai,aj) is minimal.
In the first line of standard input there is a single integer n (2 ≤ n ≤ 100,000). In the following n lines the numbers ai,a2,…,an (1 ≤ ai ≤ 1,000,000) are given, one per line.
Your program should print exactly n lines to the standard output, a single integer in each line. The i-th line should give the minimum j such that: 1 ≤ j ≤ n, j≠i and d(ai,aj)n is minimal.
6 1 2 3 4 5 6
2 1 1 2 1 2