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 $ .

The first line contains two integers $ n $ and $ k $ ( $ 2 \leq n \leq 10^5 $ , $ 2 \leq k \leq 100 $ ). The second line contains $ n $ integers $ a_1, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ).

Print a single integer — the number of suitable pairs.

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 $ .