codeforces 1225D. Power Products

Posted on | Post modified:

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;
}