A12927. 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 < 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$ ).
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.
输入输出样例
输入 #1
6 3 1 3 9 8 24 1
输出 #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$ .
- $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$ .