TopCoder SRM 611 Div1 Easy LCMSet

SRM611は不参加。
しかし出ても1ミスしていたので出なくてよかったかも…。
http://community.topcoder.com/stat?c=problem_statement&pm=12918

問題

自然数の集合Sに対し、LCM(S)とはSの要素から作られる最小公倍数をSに加える、という処理を変化がなくなるまで行ったものである。
2つの集合A,Bが与えられたとき、LCM(A)==LCM(B)かどうか判定せよ。

解法

自分の解法は以下の通り。

Sの中にすでにSの他の2要素の最小公倍数で構成できる数がある場合、その数を除いてもLCM(S)は同じとなる。
よって、Aからそのような数を除き、Bからもそのような数を除けば、どちらもLCM(A)及びLCM(B)を構成する最少の数が残るはずであり、LCM(A)==LCM(B)なら残った数も一致するはずである。

なお、想定解としてはAの最小公倍数群からBの各要素が生成でき、Bの最小公倍数群からAの各要素を生成できればLCM(A)==LCM(B)、だったようだ。

vector<int> shrink(vector<int> V) {
	int ng[51];
	int x,y,z;
	ZERO(ng);
	map<ll,int> M[51];
	
	sort(V.begin(),V.end());
	FOR(x,V.size()) {
		int vv=V[x];
		for(int a=2;a*a<=vv;a++) {
			while(vv%a==0) M[x][a]++,vv/=a;
		}
		if(vv>1) M[x][vv]++;
		
		map<ll,int> T;
		FOR(y,x) {
			int inc=1;
			ITR(it,M[y]) if(M[x].find(it->first)==M[x].end() || M[x][it->first]<it->second) inc=0;
			if(inc) ITR(it,M[y]) T[it->first]=max(T[it->first],it->second);
		}
		
		ng[x]=(T==M[x]);
	}
	
	vector<int> V2;
	FOR(x,V.size()) if(ng[x]==0) V2.push_back(V[x]);
	return V2;
}

class LCMSet {
	public:
	string equal(vector <int> A, vector <int> B) {
		if(shrink(A)==shrink(B)) return "Equal";
		else return "Not equal";
	}

};

まとめ

Easyとしては結構難しかった。