唯一分解定理（欧几里得）

唯一分解（算数基本定理）；任何一个大于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 }