codeforces 1225D. Power Products

codeforces 1225D. Power Products

题意

计算满足$a_{i}*a_{j}=x^k,i<j$的对数。

思路

考虑$x*y=p^k$,将$x$和$y$进行质因子分解可得:

如果对于$x$和$y$有着不同的质因子,那么该质因子的次数一定是$k$的倍数,如果有着相同的质因子,那么$t_i+m_i$也一定是$k$的倍数,因此,可以考虑把$a_i$进行质因子分解,将幂次模$k$后构造成新的数字即可把每个数字压缩,这样只需要考虑$t_i+m_i=k$的情况,利用map存一下然后$O(n)$的扫一遍即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
long long a[N],b[N];
typedef long long ll;
map<ll,ll> nums;
ll qp(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main(){
long long n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
ll now=1;
ll need=1;
for(ll j=2;j*j<=a[i];j++){
if(a[i]%j==0){
int cnt=0;
while(a[i]%j==0){
++cnt;
a[i]/=j;
}
cnt%=k;
now*=qp(j,cnt);
}
}
if(a[i]!=1){
now*=a[i];
}
a[i]=now;
nums[a[i]]++;
for(ll j=2;j*j<=now;j++){
if(now%j==0){
int cnt=0;
while(now%j==0){
++cnt;
now/=j;
}
need*=qp(j,k-cnt);
}
}
if(now!=1){
need*=qp(now,k-1);
}
b[i]=need;
}
ll ans=0;
for(int i=1;i<=n;i++){
if(b[i]==a[i]){
ans+=nums[b[i]]-1;
}else{
ans+=nums[b[i]];
}
}
cout<<ans/2<<endl;
return 0;
}