rt，TLE on test 6

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=31451413;
const int N=1e7+5;
int a[N];
int qp(int x,int k){
	int ans=1,base=x;
	while (k){
		if (k&1) ans*=base;
		if (ans>1e10||base>=3e9) return 0;
		base*=base;
		k>>=1;
	}
	return ans;
}
int buc[N];
int n,k;
vector<int> v;
bool f[N];
int pr[N],cnt;
void sh(int n){
	for (int i=1;i<=n;i++){
		f[i]=1;
	}
	f[1]=0;
	for (int i=2;i<=n;i++){
		if (f[i]){
			pr[++cnt]=i;
		}
		for (int j=1;j<=cnt&&i*pr[j]<=n;j++){
			f[i*pr[j]]=0;
			if (!i%pr[j]){
				break;
			}
		}
	}
}
int mp[mod+5];
int ans;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		buc[a[i]]++;
	}
	int ma=max(a[1],a[2]),sma=min(a[1],a[2]);
	for (int i=3;i<=n;i++){
		if (a[i]>=ma){
			sma=ma;
			ma=a[i];
		}
		else if (a[i]>sma) sma=a[i];
	}
	for (int i=1;;i++){
		if (k*log(i)<=log(sma*ma)) v.push_back(qp(i,k));
		else break;
	}
	if (k==2){
		sh(1e5);
		for (int i=1;i<=n;i++){
			int now=0,base=1;
			int x=a[i];
			for (int j=1;j<=cnt;j++){
				int c=0;
				while (x%pr[j]==0) c^=1,x/=pr[j];
				if (!c) c=mod-1;
				now=(now+base*c)%mod;
				base=(base*2)%mod;
			}
			mp[now]++;
		}
		for (int i=1;i<=n;i++){
			int now=0,base=1;
			int x=a[i];
			for (int j=1;j<=cnt;j++){
				int c=0;
				while (x%pr[j]==0) c^=1,x/=pr[j];
				if (!c) c=mod-1;
				now=(now+base*c)%mod;
				base=(base*2)%mod;
			}
			ans+=mp[now]+mp[mod-now-1];
		}
		goto code;
	}
	for (int c:v){
		for (int i=1;i<=n;i++){
			if (c%a[i]) continue;
			int x=c/a[i];
			ans+=buc[x];
		}
	}
	code:
	for (int i=1;i<=1e5;i++){
		if (!buc[i]) continue;
		for (int x:v){
			if (i*i==x){
				ans-=buc[i];
				break;
			}
		}
	}
	cout<<ans/2;
	return 0;
}