Irreducible Root

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 64M

Problem types

Given an array a with length N of positive integers, find the amount of unordered pairs of indices i,j\ i \neq j there are such that a_i\cdot a_j is an irreducible K^{th} root.

A K^{th} root is reducible if it has a K^{th} power other than 1 as a factor.

Input Specification

The first line will contain two integers, N\ (1 \leq N \leq 10^5), and K\ (2 \leq K \leq 30).

The next line will contain N integers, the array a\ (2 \leq a_i \leq 10^6).

Output Specification

You are to output one line, the number of unordered pairs.


Subtask 1 [30%]

N \leq 3\cdot 10^3

Subtask 2 [70%]

No further constraints.

Sample Input

4 3
2 3 4 9

Sample Output



There are no comments at the moment.