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 \lt j \leq n$, and there exists an integer $x$ such that $a_i \cdot a_j = x^k$.

给你 $n$ 个正整数 $a_1, \ldots, a_n$ 和一个整数 $k \geq 2$。请统计满足 $1 \leq i \lt j \leq n$ 且存在整数 $x$ 使得 $a_i \cdot a_j = x^k$ 的数对 $(i, j)$ 的个数。

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

第一行包含两个整数 $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$）。

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

在样例中，符合条件的数对有：

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