Codeforces Round #596 Div. 2 D. Power Products 唯一分解+哈希
程序员文章站
2022-06-02 12:38:07
...
Codeforces Round #596 Div. 2 D. Power Products 唯一分解+哈希
链接:Power Products
还是自己太菜,想了一天没有想到对分解之后的结果如何进行简单的处理,看了一眼大佬的代码,真是自叹不如。
题解:先对每个数进行唯一分解,对分解出来的数进行模存储,然后哈希保存,用于查询。因为题目要求两个数的乘积是一个数的次幂,所以对两个数唯一分解,所有幂次相加之后模应该等于。所以我们就可以查找一个数唯一分解之后,对幂次模之后的关于模的补数(我也不知道这个数叫什么名字,暂且叫模k的补数吧)的哈希,进行相加统计。形式如:p模的补数。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+100;
map<vector<pair<int,int> >, int> ma;
int main()
{
int n, k,x;
scanf("%d%d", &n, &k);
LL ans = 0;
for(int i = 0;i <n;i++)
{
scanf("%d",&x);
vector<pair<int,int> > ve1, ve2;
for(int j = 2; j*j<=x;j++)//唯一分解
{
if(x%j==0)
{
int cnt = 0;
while(x%j==0)
{
cnt++;
x/=j;
}
if(cnt%k)
{
ve1.push_back(make_pair(j,cnt%k));//对唯一分解结果保存
}
}
}
if(x!=1)
{
ve1.push_back(make_pair(x,1));
}
int siz = ve1.size();
for(int j = 0; j < siz; j++)//求模k的补数
{
ve2.push_back(make_pair(ve1[j].first, k-ve1[j].second));
}
ans = ans+ma[ve2];//先查询,后保存,防止出现原数和补数一样
ma[ve1]++;
}
printf("%lld\n", ans);
return 0;
}