D. Произведения-степени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано $$$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
Примечание

В примере подходят следующие пары:

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