Вам дано \(n\) целых положительных чисел \(a_1, \ldots, a_n\) и целое \(k \geq 2\). Посчитайте количество пар \(i, j\), таких что \(1 \leq i < j \leq n\), а также существует целое \(x\), такое что \(a_i \cdot a_j = x^k\).
В первой строке записано два целых числа \(n\) и \(k\) (\(2 \leq n \leq 10^5\), \(2 \leq k \leq 100\)).
Во второй строке записано \(n\) целых чисел \(a_1, \ldots, a_n\) (\(1 \leq a_i \leq 10^5\)).
Выведите одно число — количество подходящих пар.
В примере подходят следующие пары:
6 3 1 3 9 8 24 1
5
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач