【codeforces 1225D】Power Products

题意

计算满足$a_i\ast a_j=x^k,i<j$的对数。

思路

考虑$x\ast y=p^k$，将$x$和$y$进行质因子分解可得:
$$x=p_1^{m_1}{p}_2^{m_2}{p}_3^{m_3}...p_n^{m_n}$$
$$y=q_1^{t_1}{q}_2^{t_2}{q}_3^{t_3}...q_n^{t_n}$$

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

代码

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

最后

以上就是迅速耳机为你收集整理的【codeforces 1225D】Power Products的全部内容，希望文章能够帮你解决【codeforces 1225D】Power Products所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。