题意：
给出长度为n的序列和k，问有多少个数对( i , j )满足a i ∗ a j = x k
思路：
首先，对所有的数分解质因子。当a i和a j a的质因子对应的指数之和m o d k = = 0的时候，是一对合法的数对。
问题就转化成了如何快速判断。
大概有两种方法，一是选择用m a p , v e c t o r嵌套判断，二是用哈希。
暂且不怎么会第一种所以写了哈希，对每个数分解出来的质因子的指数都m o dk，得到结果t t ,如果t t不为0的话，就让该数加上质因子的t t次方。就算出这个数的哈希值后，用m a p维护个数。再用同样的方法求互补的哈希值，计算跟当前数满足条件的数对个数。
哈希的思路太妙了。
代码：
#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 */
