← 返回题目列表

Codeforces · 1225/D

D. 电源产品

中文机器翻译题面 查看原题

给你 $$$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$$$)。

输出

打印一个整数——合适的对的数量。

示例

输入 #1

6 3
1 3 9 8 24 1

输出 #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$$$。