唯一分解（算数基本定理）；任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积P1^a1*P2^a2*...Pn^an,这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。最早证明是由欧几里得给出的。（扩展：交换代数）
例题：Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2) D. Power Products （唯一分解+哈希）
题意：找有几对（ai，aj）使得ai*aj=x^k;中的x存在为正整数；
如果两个数的质因数分解后的每个数的因子个数都是k的倍数，那么就说明有解（c++的stl是个超级神奇的东西）
题解：暴力分别对ai,aj进行质因数分解，对质因数的个数进行模k存储，然后哈希保存，用于查询，题目要求找x，那么对ai和aj唯一分解之后，他们因子的所有次幂之和 模k应为0，所以我们就可以查找一个数唯一分解之后，对幂次模k之后的剩下的数（k-（p%k）） 进行哈希相加统计。
code；
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+10; 4 int n,k; 5 int a[maxn]; 6 map<vector<pair<int,int> >,int> mp; 7 int main() 8 { 9 scanf("%d%d",&n,&k); 10 for(int i=0; i<n; i++) 11 scanf("%d",&a[i]); 12 long long ans=0; 13 for(int i=0; i<n; i++) 14 { 15 vector<pair<int,int> >v1; 16 for(int cur=2; cur*cur<=a[i]; cur++) 17 { 18 int num=0; 19 while(a[i]%cur==0) 20 { 21 a[i]/=cur; 22 num++;//找质因数的个数 23 } 24 if(num%k) 25 v1.push_back(make_pair(cur,num%k));//每个质因数的个数有几个 26 } 27 if(a[i]>1) 28 v1.push_back(make_pair(a[i],1)); 29 vector<pair<int,int> > v2; 30 for(int j=0; j<v1.size(); j++) 31 { 32 v2.push_back(make_pair(v1[j].first,k-v1[j].second)); 33 } 34 ans+=mp[v2]; 35 mp[v1]++; 36 } 37 cout<<ans<<endl; 38 //system("pause"); 39 return 0; 40 41 }
原文：https://www.cnblogs.com/sweetlittlebaby/p/12723534.html