题目链接在这里:Problem - H - Codeforces
这题思路不难想,将每个数分解质因数之后,如果有两个数,对应质因数的次数加起来正好是k的倍数,那这两个就是符合的,也就是说这两个数要形成一个互补的关系,用数组来实现的话会比较麻烦,使用map映射函数配合vector容器会简化很多
不得不说映射函数map是个非常牛批的东西,连vector都能映射!
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1e5+5; 5 LL n,k,a[MAX],ans; 6 vector <pair<LL,LL> >x,y; 7 map<vector<pair<LL,LL> >,LL> b; 8 int main(){ 9 freopen ("h.in","r",stdin); 10 freopen ("h.out","w",stdout); 11 LL i,j,zt,cnt; 12 scanf("%lld%lld",&n,&k); 13 for (i=1;i<=n;i++) scanf("%lld",a+i); 14 for (i=1;i<=n;i++){ 15 zt=a[i]; 16 x.clear(),y.clear(); 17 for (j=2;j*j<=zt;j++){ 18 cnt=0; 19 while (zt%j==0){ 20 cnt++; 21 zt/=j; 22 } 23 cnt%=k; 24 if (cnt==0) continue; 25 x.push_back(make_pair(j,cnt)); 26 y.push_back(make_pair(j,k-cnt)); 27 } 28 if (zt!=1){ 29 x.push_back(make_pair(zt,1)); 30 y.push_back(make_pair(zt,k-1)); 31 } 32 ans+=b[y]; 33 b[x]++; 34 } 35 printf("%lld",ans); 36 return 0; 37 }