传送门
题意:求n个数中满足 得对数
n<1e5,a[i]<1e5,2<=k<=100
STL!想到把每个数拆成素数的乘积得形式后 得到a[i]=p1^k1 (**) p2 ^k2…
那么对应满足条件得aj=p1^(K1)(*) p2 ^k2…
其中(k1+K1)%k==0
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
typedef pair<int,int> p;
map<vector<p>,int>mp;
bool prime[100010]={0};
void init()
{
memset(prime,1,sizeof prime);
for(int i=2;i<=100000;i++){
if(prime[i]){
for(int j=i+i;j<=100000;j+=i)prime[j]=0;
}
}
//for(int i=1;i<=10;i++) if(!prime[i]) cout<<i<<endl;
}
int main()
{
init();
int n,k,d;L ans=0;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&d);
vector<p>v1,v2;
for(int j=2;j<=d;j++){
if(prime[d]){break;}
int cnt=0;
while(d%j==0){
d/=j;
cnt++;
}
if(cnt%k) v1.push_back(make_pair(j,cnt%k));
}
if(d>1) v1.push_back(make_pair(d,1));
int l=v1.size();//c//out<<i<<","<<endl;
for(int j=0;j<l;j++){
v2.push_back(make_pair(v1[j].first,k-v1[j].second));
//cout<<v1[j].first<<","<<k-v1[j].second<<endl;
}
ans=ans+1ll*mp[v2];
mp[v1]++;
//cout<<ans<<endl;
}
printf("%lld\n",ans);
}