1225DPower Products(质因数分解的变形应用)

题意：传送门 题解：这样考虑，如果一个数是$x^k$的形式，那么质因数分解完成后，肯定是$p_1^{(k\ast cn{t}_1)}\ast p_2^{(k\ast cn{t}_2)}\ast p_2^{(k\ast cn{t}_2)}\ast \dots$其中$cn{t}_i$一定是个非负数，那么考虑两个数相乘起来，其中一个数进行质因数分解后，质因子上是$k$的倍数的是不用弥补的，反而那些不够$k$的需要进行与两外一个数乘起来进行弥补来达到$k$的倍数，那么就将这些数重新考虑为两个数，其中一个就是将质因子为$k$的倍数的去除，留下实际起作用的，同时也记录它需要什么数进行弥补。

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+5; ll n,k,a[N],b[N]; map<ll,ll>mp; ll qpow(ll a,ll b){ll ans=1ll;for(ll i=b;i;i>>=1,a=a*a)if(i&1)ans=ans*a;return ans;} int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ ll now=1,need=1; for(int j=2;j<=sqrt(a[i]);j++){ int cnt=0; if(a[i]%j==0){ while(a[i]%j==0)a[i]/=j,cnt++; } cnt%=k; now=now*qpow(j,cnt); if(cnt!=0)need=need*qpow(j,k-cnt); } if(a[i]!=1){ now=now*a[i];need=need*qpow(a[i],k-1); } a[i]=now;b[i]=need; mp[a[i]]++; } ll ans=0; for(int i=1;i<=n;i++){ if(a[i]==b[i])ans+=mp[a[i]]-1; else ans+=mp[b[i]]; } printf("%lld\n",ans/2); return 0; }