Subtask 1: ~N \leq 14~.

• Duyệt ~2^n~ cách chọn. Với mỗi cách chọn, ta duyệt từng cặp số và kiểm tra với điều kiện đề bài.
• Do các giá trị ~a_i~ có thể rất lớn, ta không thể lũy thừa cặp ~a_i \times a_j~ lên ~K~ lần. Thay vào đó, do ~K \leq 5~, ta có thể lưu hết các lũy thừa bậc ~K~ vào một vector, và tìm kiếm nhị phân trên đó.

ĐPT: ~O(2^N \times N^2 \times \log MAX_A)~.

Subtask 2: ~N \leq 20~.

• Đánh giá độ phức tạp của subtask 1, ta nhận thấy có thể cắt bỏ một vòng for ~N~.
• Khi xét đến ~mask~, ta có thể tìm các bit ~i~ đang tắt của ~mask~ và kiểm tra tích các ~a_i \times a_j~, với ~j~ là bit bật của ~mask~ đó. Việc kiểm tra có thể lưu trước bằng một mảng ~N \times N~.

ĐPT: ~O(2^N \times N + N^2 \times \log MAX_A)~.

Subtask 3 + 5: ~K = 2~.

• Đến đây ta cần biết về biểu diễn square-free của một số nguyên dương. Giả sử số nguyên dương ~X~ có thể được biểu diễn dưới dạng ~p_1^{q_1} \times p_2^{q_2} \times \dots \times p_k^{q_k}~, ta dễ thấy ta chỉ cần quan tâm các thừa số nguyên số có số mũ lẻ. Khi đó hai số ~X, Y~ có tích là số chính phương khi và chỉ khi biểu diễn square-free của ~X~ và ~Y~ bằng nhau.
• Gọi ~B_i~ là biểu diễn square-free của ~A_i~, ta có thể gộp các nhóm có ~B_i~ bằng nhau và chọn tối đa 1 phần tử trong mỗi nhóm đó.

ĐPT: ~O(N \times \log \log N + N \times \log N)~.

Subtask 3 + 4: ~N \leq 2000~.

• Đến đây ta có thể biểu diễn dãy dưới dạng một đồ thị ~N~ đỉnh, ~O(N^2)~ cạnh. Cụ thể, ta nối hai đỉnh ~i, j~ nếu tích của chúng không là một lũy thừa bậc ~K~. Đáp án là thành phần liên thông lớn nhất.

ĐPT: ~O(N^2)~.

Subtask 6: Không có ràng buộc gì thêm.

• Phát triển từ ~K = 2~, ta có thể biểu diễn các số ~A_i~ dưới dạng k-free, tức trong phân tích nguyên tố không chứa ước là lũy thừa bậc ~K~. Khi đó, hai số ~X, Y~ có tích là một lũy thừa bậc ~K~ khi và chỉ khi biểu diễn k-free của chúng "đối nhau", tức trái ngược nhau khi xét mod ~K~.
• Đến đây, với tập các số có k-free bằng ~i~, ta chỉ cần so sánh với tập đối của ~i~ và chọn tập có size lớn hơn.
• Ngoài ra, bài còn có một số trường hợp đặc biệt như ~inv(i) > 2 \times 10^6~, ~inv(i) = 1~ hoặc ~inv(i) = i~, chi tiết xem tại code.

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

const int maxn = 2e5 + 5;
const int N = 2e6 + 6;
int n, a[maxn], s[N];
int k;
int b[maxn];
int inv[N];
int save[N];

bool vis[N];

void solve() {
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    int x = a[i];
    b[i] = 1;
    long long alt = 1;
    while(x > 1) {
      int dak = s[x];
      int cnt = 0;
      while(x % dak == 0) {
        x /= dak;
        ++cnt;
      }
      cnt %= k;
      for(int j = 1; j <= cnt; ++j) {
        b[i] *= dak;
      }
      cnt = (k - cnt) % k;
      for(int j = 1; j <= cnt; ++j) {
        alt *= dak;
        if(alt > N) {
          alt = 0;
        }
      }
    }
    inv[b[i]] = alt;
    ++save[b[i]];
    // debug(i, b[i], alt);
  }
  int ans = 0;
  int perfect_expo = 0;
  for(int i = 1; i < N; ++i) {
    if(inv[i] == 0) {
      ans += save[i];
      continue;
    }
    if(inv[i] == 1) {
      perfect_expo += save[i];
      vis[i] = 1;
      continue;
    }
    if(vis[i] || vis[inv[i]] || !save[i]) continue;
    // debug(i, save[i], save[inv[i]]);
    if(i == inv[i]) {
      ++ans;
      vis[i] = 1;
      continue;
    }
    if(save[i] < save[inv[i]]) {
      ans += save[inv[i]];
      vis[inv[i]] = 1;
    }
    else {
      ans += save[i];
      vis[i] = 1;
    }
  }
  ans += (perfect_expo > 0);
  if(ans == 0) 
    cout << -1;
  else 
    cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  for(int i = 2; i * i < N; ++i) {
    if(!s[i]) {
      for(int j = i * i; j < N; j += i) 
        s[j] = i;
    }
  }
  for(int i = 2; i < N; ++i) {
    if(!s[i]) 
      s[i] = i;
  }
  solve();

  return 0;
}