TopCoder SRM 814 : Div1 Medium DevuAndEqualizingLCM

これもさほど難しくはないね…。
https://community.topcoder.com/stat?c=problem_statement&pm=13752&rd=18888

問題

2つの整数列A,Bが与えられる。
Bのいくつかの要素を任意の整数にし、LCM(A)=LCM(B)となるようにしたい。
値を変更すべき最小要素数はいくつか。

解法

まずLCM(A)を素因数分解したものを求めておく。
次に、Bをそれぞれ素因数分解し、ある素因数がLCM(A)より次数が大きい場合、その要素は(次数を下げるため)値の変更必須である。

コーナーケースとして、B中に次数を下げる必要のある素因数をもつ要素が1個もない場合、かつLCM(A)!=LCM(B)の時は、1要素だけ値を書き換えてLCM(A)=LCM(B)にする必要がある。

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	
	FORR(p,prime) {
		while(n%p==0) V[p]++, n/=p;
	}
	if(n>1) V[n]++;
	return V;
}

class DevuAndEqualizingLCM {
	public:
	int minimumOperationsNeeded(vector<long long> A, vector<long long> B) {
		map<ll,int> ma,ma2;
		cprime();
		FORR(a,A) {
			auto P=enumpr(a);
			FORR(b,P) ma[b.first]=max(ma[b.first],b.second);
		}
		
		int need=0;
		
		FORR(b,B) {
			auto P=enumpr(b);
			FORR(c,P) ma2[c.first]=max(ma2[c.first],c.second);
			FORR(c,P) {
				if(c.second>ma[c.first]) {
					need++;
					break;
				}
			}
		}
		
		if(need==0) {
			if(ma!=ma2) need++;
		}
		return need;
	}
}

まとめ

まぁ400ptだしね。