题意：
给出长度为\(n\)的序列和\(k\)，问有多少个数对\((i,j)\)满足\(a^i*a^j=x^k\)
思路：
首先，对所有的数分解质因子。当\(a_i\)和\(a_j\)的质因子对应的指数之和\(\mod k==0\)的时候，是一对合法的数对。
问题就转化成了如何快速判断。
大概有两种方法，一是选择用\(map,vector\)嵌套判断，二是用哈希。
暂且不怎么会第一种所以写了哈希，对每个数分解出来的质因子的指数都\(\mod k\)，得到结果\(tt\),如果\(tt\)不为\(0\)的话，就让该数加上质因子的\(tt\)次方。就算出这个数的哈希值后，用\(map\)维护个数。再用同样的方法求互补的哈希值，计算跟当前数满足条件的数对个数。
哈希的思路太妙了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn=1e5+7,maxm=1e6+7,mod=1e9+7;
const int inf=0x3f3f3f3f;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;}
int n,k,a[maxn];
int prime[maxn],cnt,vis[maxn];
void init(){
vis[1]=1;
for(int i=2;i<=1e5;i++){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=1e5;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
map<ll,ll>mp;
int main(){
init();
// cout<<cnt<<endl;
n=read,k=read;
ll ans=0;
rep(i,1,n){
a[i]=read;
ll now=1,tmp=a[i];
for(int j=1;j<=cnt;j++){
ll tt=0;
if(tmp==1) break;
while(tmp%prime[j]==0){
tmp=tmp/prime[j];
tt++;
}
tt=tt%k;
if(tt) now=now*qpow(prime[j],tt);
}
if(tmp>1) now=now*tmp;
a[i]=now;
now=1,tmp=a[i];
mp[a[i]]++;
for(int j=1;j<=cnt;j++){
ll tt=0;
if(tmp==1) break;
while(tmp%prime[j]==0){
tmp=tmp/prime[j];
tt++;
}
tt=tt%k;
if(tt) now=now*qpow(prime[j],k-tt);
}
if(tmp>1) now=now*qpow(tmp,k-1);
ans=ans+mp[now];
if(now==a[i]) ans--;
}
printf("%lld\n",ans);
return 0;
}
/*
6 3
1 3 9 8 24 1
*/