D. Power Products
hashing; math; number theory
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\).