Codeforces #596 Div1 B. Power Products

これ750ptでもいい気がする。
http://codeforces.com/contest/1246/problem/B

問題

整数列Aが与えられる。
正整数Kが与えられるので、要素の対のうち、ある整数のK乗になるものが何組あるか求めよ。

解法

各要素素因数分解し、かつ次数をmod K取っておく。
(素因数,K-次数)のvectorをmapに乗せておけば、(素因数,次数)のvectorで参照して対応する要素の数を高速に求められる。

int N,K;
ll A[101010];
ll ret;

vector<pair<int,int>> enumpr(ll n) {
	vector<pair<int,int>> V;
	for(int i=2;i*i<=n;i++) if(n%i==0) {
		V.push_back({i,0});
		while(n%i==0) V.back().second++,n/=i;
		V.back().second %= K;
		if(V.back().second==0) V.pop_back();
	}
	if(n>1) V.push_back({n,1});
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	map<vector<pair<int,int>>,int> M;
	FOR(i,N) {
		cin>>A[i];
		//A[i]=i+1;
		
		vector<pair<int,int>> X=enumpr(A[i]);
		vector<pair<int,int>> Y=X;
		FORR(c,Y) c.second=K-c.second;
		ret+=M[Y];
		M[X]++;
		
	}
	
	
	
	cout<<ret<<endl;
	
}

まとめ

これDiv1Bで出す内容かなぁという気がする。
実際AとAC数あんまり変わらないしね。