Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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 3 9 8 24 1
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$$$.
Codeforces (c) Copyright 2010-2020 Mike Mirzayanov