CF1225D Power Products

You are given $ n $ positive integers $ a_1, \ldots, a_n $ , and an integer $ k \geq 2 $ . Count the number of pairs $ i, j $ such that $ 1 \leq i < j \leq n $ , and there exists an integer $ x $ such that $ a_i \cdot a_j = x^k $ .

N/A

N/A

In the sample case, the suitable pairs are: - $ a_1 \cdot a_4 = 8 = 2^3 $ ; - $ a_1 \cdot a_6 = 1 = 1^3 $ ; - $ a_2 \cdot a_3 = 27 = 3^3 $ ; - $ a_3 \cdot a_5 = 216 = 6^3 $ ; - $ a_4 \cdot a_6 = 8 = 2^3 $ .