前言废话：最近一直调参…鸽了好久训练… 这个题也是神奇，以前我都不知道质因数分解能logn，以为要sqrt(n)…
给一个长度为 n 的序列 (1 <=ai <=100000，2<=n<=100000) ，给定一个整数 m (2<=m<=100) ，要求 i< j，且 ai * aj = x^m 的对数，其中 x 是正整数。
预处理每个数的最小质因数，可以logn分解一个数的质因数。另外，容易想到，如果 aiaj = x^k ，那么 aiaj的质因数的次方一定是 k 的整数倍，因此，从前往后扫的过程中，顺便处理出每个数的质因数分解，然后将他们的次方模m，求出对应的数字，和自己，在map里面查找更新即可。
贴一下这个神奇的代码。
#include<bits/stdc++.h> using namespace std; #define maxn 100005 #define maxm 1006 #define ll long long int #define INF 0x3f3f3f3f #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) #define mem(a) memset(a,0,sizeof(a)) #define sqr(x) (x*x) #define inf (ll)2e18+1 #define PI acos(-1) #define mod 10007 #define auto(i,x) for(int i=head[x];i;i=ed[i].nxt) ll read(){ ll x=0,f=1ll;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f*x; } int n,m,a[maxn]; bool vis[maxn]; int prim[maxn],cnt,fist[maxn]; void init(){ inc(i,2,maxn-1){ if(vis[i]==0)prim[++cnt]=i,fist[i]=i; for(int j=1;j<=cnt&&prim[j]*i<maxn;j++){ vis[prim[j]*i]=1; fist[prim[j]*i]=prim[j]; if(i%prim[j]==0)break; } } } unordered_map<ll,int>mp; int main() { init(); n=read();m=read(); inc(i,1,n)a[i]=read(); ll ans=0; inc(i,1,n){ vector<pair<int,int> >P; int res=a[i]; while(res!=1){ int p=fist[res]; if(P.size()==0||P.back().first!=p)P.push_back(make_pair(p,1)); else P.back().second++; res/=p; } ll x=1ll,y=1ll; for(int j=0;j<P.size();j++){ inc(k,1,P[j].second%m)x*=P[j].first; inc(k,1,(m-((P[j].second)%m))%m)y*=P[j].first; } if(y<maxn)ans+=mp[y]; mp[x]++; } printf("%lld\n",ans); return 0; }