2019-11-06
传送门：：https://codeforces.com/contest/1247/problem/D
题意：：有多少种组合方式满足乘积可以同x^k表示（k>=2）
思路：：质因数分解，任何一个合数都可以拆成几个质因数之积；
对于一个数而言 拆解后可表示成 p1^k1 * p2^k2 * p3^k3······当k1,k2 ······满足为k的倍数时我们可以不用考虑，而对那些不为k的倍数的数我们是不是该想办法从其他数中找能配对成k的倍数的数，这样组合就存在了。
详情见代码：：
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int maxn=1e5+5; 5 6 ll a[maxn],b[maxn]; 7 ll qpow(ll x,int p) 8 { 9 ll ans=1; 10 while(p){ 11 if(p&1){ans=ans*x;} 12 x=x*x; 13 p>>=1; 14 } 15 return ans; 16 } 17 map<ll,ll>mp; 18 int main() 19 { 20 int n,k; 21 scanf("%d%d",&n,&k); 22 for(ll i=1;i<=n;i++){ 23 scanf("%lld",&a[i]); 24 } 25 for(ll i=1;i<=n;i++){ 26 ll now=1,need=1; 27 for(ll j=2;j<=sqrt(a[i]);j++){//质因数分解 28 int ant=0; 29 if(a[i]%j==0){ 30 while(a[i]%j==0){ 31 a[i]/=j;ant++; 32 } 33 } 34 ant%=k; 35 now*=qpow(j,ant);//记录可用于弥补的值 36 if(ant!=0){need*=qpow(j,k-ant);}//不为k倍数时需要进行弥补的数 37 } 38 if(a[i]!=1){ 39 now*=a[i];need*=qpow(a[i],k-1);//同上 40 } 41 a[i]=now;b[i]=need; 42 mp[a[i]]++; 43 } 44 ll ans=0; 45 for(int i=1;i<=n;i++){ 46 if(a[i]==b[i]){ans+=mp[a[i]]-1;}//这种情况为本身就可以表示成x^k的形式 47 else{ans+=mp[b[i]];}//寻找弥补的数 48 } 49 printf("%lld\n",ans/2); 50 return 0; 51 }