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$.

Input

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$).

Output

Print a single integer — the number of suitable pairs.

Example input

6 3
1 3 9 8 24 1

output

5

Note

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$.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
const int MAX = 100010;
vector<int> p(MAX);
iota(p.begin(), p.end(), 0);
for (int i = 2; i < MAX; i++) {
    if (p[i] == i) {
      for (int j = i + i; j < MAX; j += i) {
        if (p[j] == j) {
          p[j] = i;
        }
      }
    }
  }
  int n, k;
  cin >> n >> k;
vector<int> cnt(MAX);
long long ans = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
int res = 1;
long long ask = 1;
while (x > 1) {
int y = p[x];
int cc = 0;
while (x % y == 0) {
x /= y;
++cc;
}
cc %= k;
for (int j = 0; j < cc; j++) {
        res *= y;
      }
      for (int j = 0; j < (k - cc) % k; j++) {
        ask *= y;
        ask = min(ask, MAX - 1LL);
      }
    }
    ans += cnt[ask];
    ++cnt[res];
  }
  cout << ans << '\n';
  return 0;
}