解题思路： 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; }