power products

解题思路：
tle思路：计算出每个值出现的次数，然后枚举x ，因为我看乘机最大也才1e10嘛 ，但是不行，当k=2的时候会卡，别的情况应该不会。哎，，

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
map<ll,int>mp;
ll qmi(ll a,int b)
{
   
	ll res=1;
	while(b)
	{
   
		if(b&1)  res=res*a;
		a = a*a;
		b>>=1;
	}
	return res;
}
int main()
{
   	
	int n,k;
	cin>>n>>k;
	ll maxv=0;
	for(int i=1;i<=n;i++)
		{
   
			cin>>a[i];
			mp[a[i]]++;
			maxv=max(maxv,a[i]);
		}
	ll res=0;
	ll ans2=0;
	for(int i=1;;i++)
	{
   
		ll tt=qmi(i,k);
		if(tt>maxv*maxv)	break;
		for(auto it:mp)
		{
   
			ll z = it.first;
			ll y = it.second;
			if(tt%z==0)
			{
   
				ll zz = tt/z;
				if(zz!=z)
					res+=y*mp[zz];
				else
					ans2+=mp[zz]*(mp[zz]-1)/2;
			} 
		}
	}
	cout<<res/2 + ans2	<<endl;
	return 0;

}

正确思路：我看了一个用哈希解决的方法，将所有数质因数分解，如果乘积是x的k次，那么他们每个质因数的幂一定是k的整数倍，我们将每个质因数的次数哈希，然后开一个bhash用来计算和它相补的值，最后用个map来查询bash哈希值对应的次数，最后加起来就是答案。

/*#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
map<ll,int>mp;
ll qmi(ll a,int b)
{
   
	ll res=1;
	while(b)
	{
   
		if(b&1)  res=res*a;
		a = a*a;
		b>>=1;
	}
	return res;
}
vector<ll>Q;
int main()
{
   	
	int n,k;
	cin>>n>>k;
	ll maxv=0;
	for(int i=1;i<=n;i++)
		{
   
			cin>>a[i];
			mp[a[i]]++;
			maxv=max(maxv,a[i]);
		}
	ll res=0;
	ll ans2=0;
	for(int i=1;;i++)
	{
   
		ll tt = qmi(i,k);
		if(tt>maxv * maxv)	break;
		Q.push_back(tt);
	}
	for(int i=0;i<Q.size();i++)
	{
   
		ll tt=Q[i];
		if(tt>maxv*maxv)	break;
		for(auto it:mp)
		{
   
			ll z = it.first;
			ll y = it.second;
			if(z*z>tt)	break;
			if(tt%z==0)
			{
   
				ll zz = tt/z;
				if(zz!=z)
					res+=y*mp[zz];
				else
					ans2+=mp[zz]*(mp[zz]-1)/2;
			} 
		}
	}
	cout<<res + ans2	<<endl;
	return 0;

}*/
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
typedef unsigned long long ull;
ull base = 131;
ull Hash[N];
int prime[N];
int cnt;
bool st[N];
int n,k;
int primeid[N];
void init()
{
   
	for(int i=2;i<N;i++)
	{
   
		if(!st[i])
			{
   
				primeid[i]=cnt;
				prime[cnt++]=i;
			}
		for(int j=0;i*prime[j]<=N-1;j++)
		{
   
			if(i%prime[j]==0)	break;
			st[i*prime[j]]=true;

		}
	}
}
map<ull,int>mp;
ll qmi(ll a,int b)
{
   
	ll res=1;
	while(b)
	{
   
		if(b&1)  res=res*a;
		a = a*a;
		b>>=1;
	}
	return res;
}
int work(int u)
{
   
	ll p = a[u];
	ull xhash=0;
	ull bhash=0;
	for(int i=0;i<cnt;i++)
	{
   
		if(prime[i]*prime[i]>p)	break;
		if(p%prime[i]==0)
		{
   
			int pcnt=0;
			while(p%prime[i]==0)
			{
   
				p/=prime[i];
				pcnt++;
				if(pcnt>=k)
					pcnt-=k;
			}
			xhash+=pcnt*Hash[i+1];
			bhash+=((k-pcnt)%k+k)%k*Hash[i+1];
		}
	}
	if(p!=1)
	{
   
		xhash+=1*Hash[primeid[p]+1];
		bhash+=(k-1)*Hash[primeid[p]+1];
	}
	ll	res=mp[bhash];
	mp[xhash]++;
	return res;
}
int main()
{
   	
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
   
		cin>>a[i];
	}
	Hash[0]=1;
	init();
	//cout<<cnt<<endl;
	for(int i=1;i<cnt;i++)
		Hash[i]=Hash[i-1]*base;;
	ll res=0;
	for(int i=n;i>=1;i--)
		res+=work(i);
	cout<<res<<endl;
	return 0;

}