一个比较偏门的做法，当 $k=2$ 的时候它的时间复杂度是 $O(n\sqrt n)$，$k>2$ 的时候它的时间复杂度是 $O(n\cdot n^{\frac{2}{k}})$，按理来说是能过的。

但是对于 test11 ($n=10^5,k=3$)，它被卡常 TLE 了，下面贴出代码，求各位大神卡常（）

#include <bits/stdc++.h>
using namespace std;
 
#define int unsigned long long
 
const int MAXN = 214514;
int n, k, maxa, cnt;
int a[MAXN];
vector<int> exist[MAXN], valid;
map<int, int> appear_cnt;
 
int Quick_Pow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a *= a)
		if (b & 1)
			res *= a;
	return res;
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 0; i < n; i += 1) {
		cin >> a[i];
		exist[a[i]].push_back(i);
		maxa = max(maxa, a[i]);
	}
	if (k >= 34)
		valid.push_back(1);
	else
		for (int i = 1, x = Quick_Pow(i, k); x <= maxa * maxa; i += 1, x = Quick_Pow(i, k))
			valid.push_back(x);
	if (k == 2) {
		for (int i = 0; i < n; i += 1)
			for (int j = 2; j * j <= a[i]; j += 1)
				while (a[i] % (j * j) == 0)
					a[i] /= (j * j);
		for (int i = 0; i < n; i += 1) {
			cnt += appear_cnt[a[i]];
			appear_cnt[a[i]] += 1;
		}
	} else {
		for (int i = 0; i < valid.size(); i += 1) {
			for (int j = 0; j < n; j += 1) {
				if (valid[i] <= maxa * a[j]) {
					const vector<int> &temp = exist[valid[i] / a[j]];
					if (valid[i] % a[j] == 0 && !temp.empty())
						cnt += temp.end() - upper_bound(temp.begin(), temp.end(), j);
				}
			}
		}
	}
	cout << cnt;
	return 0;
}