传送门 题意：求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); }