暑假集训Day12 H (数论 STL)

题目链接在这里: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 }

 

上一篇:day12


下一篇:SQL Server的“错误:9004”