CF1468L Prime Divisors Selection

Suppose you have a sequence of $ k $ integers $ A = [a_1, a_2, \dots , a_k] $ where each $ a_i \geq 2 $ . A sequence of prime integers $ P = [p_1, p_2, \dots, p_k] $ is called suitable for the sequence $ A $ if $ a_1 $ is divisible by $ p_1 $ , $ a_2 $ is divisible by $ p_2 $ and so on. A sequence of prime integers $ P $ is called friendly if there are no unique integers in this sequence. A sequence $ A $ is called ideal, if each sequence $ P $ that is suitable for $ A $ is friendly as well (i. e. there is no sequence $ P $ that is suitable for $ A $ , but not friendly). For example, the sequence $ [2, 4, 16] $ is ideal, while the sequence $ [2, 4, 6] $ is not ideal (there exists a sequence $ P = [2, 2, 3] $ which is suitable for $ A $ , but not friendly). You are given $ n $ different integers $ x_1 $ , $ x_2 $ , ..., $ x_n $ . You have to choose exactly $ k $ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

N/A

N/A