A12927 | $Power Products$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

输入 #1

6 3
1 3 9 8 24 1

输出 #1

C++ 编辑器

输入

输出