Technocup 2020 - Elimination Round 2 |
---|
Finished |
You are given n positive integers a1,…,an, and an integer k≥2. Count the number of pairs i,j such that 1≤i<j≤n, and there exists an integer x such that ai⋅aj=xk.
The first line contains two integers n and k (2≤n≤105, 2≤k≤100).
The second line contains n integers a1,…,an (1≤ai≤105).
Print a single integer — the number of suitable pairs.
6 3 1 3 9 8 24 1
5
In the sample case, the suitable pairs are:
Name |
---|