本文主要是介绍Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2) D. Power Products(数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1247/problem/D
题目大意：给n个数字，问有多少对数字的乘积是某个数字的k次方
题目思路：很明显，一个数字的k次方需要满足的条件是他的每个质因数的幂次都是k的倍数，那么只要得出当前质因数的幂次情况，看看能把所有质数的幂次都补成k的倍数的数字个数就行
这里唯一想不到的点就是map居然能套一个vector，vector里面再能套一个pair，实在太神奇了！
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 2e5+5;
const int MOD = 1e9+7;
int n,k;
int x;
map<vector<pair<int,int> >,int>mp;
vector<pair<int,int> >v;
pair<int,int>p;
int main(){while(cin>>n>>k){mp.clear();ll ans=0;rep(i,1,n){v.clear();cin>>x;rep(i,2,sqrt(x)){if(x%i==0){int num=0;while(x%i==0)num++,x/=i;num%=k;if(num){p.first=i,p.second=num;v.push_back(p);}}}if(x!=1){p.first=x,p.second=1;v.push_back(p);}ans+=mp[v];int len=v.size();rep(i,0,len-1){v[i].second=k-v[i].second;}mp[v]++;}cout<<ans<<endl;}return 0;
}
这篇关于Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2) D. Power Products(数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
