Power Products

现在给你$n$个正整数 $[a_1,a_2,...,a_n]$ 和一个的正整数$k\geq2$，现在请你求出有多少组 $(i,j)$ ，满足 $(1≤i<j≤n)$且存在一个整数 $x$ 满足 $a_i\times a_j=x^k$ ### 输入格式 输入第一行是两个正整数$n$和$k$$(2≤n≤10^5,2≤k≤100)$ 第二行为$n$个正整数$[a_1,a_2,...,a^n](1≤a_i≤10^5)$ ### 输出格式 输出一个整数，表示有多少满足条件的组合 ### 样例说明 样例中有以下几组满足条件的组合 $a_1*a_4=8=2^3$ $a_1*a_6=1=1^3$ $a_2*a_3=27=3^3$ $a_3*a_5=216=6^3$ $a_4*a_6=8=2^3$ 一共五组，所以输出为$5$

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.

6 3
1 3 9 8 24 1

5

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