Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Вам дано $$$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$$$).