yukicoder : No.3270 No Coprime Cycles

最初問題の理解にちょっと手間取った。
https://yukicoder.me/problems/no/3270

問題

整数列Bに対する無向グラフg(B)を以下のように定める。

• Bの各要素に対応する|B|個の点を持つグラフである。
• B[i]とB[j]に2以上の公約数dがある場合、点i,jをラベルdの辺で結ぶ。同じ2点間を、ラベルの異なる複数の辺が結ぶこともある。

整数列Aが与えられる。g(A)に対し、長さ2以上の閉路において、各辺のラベルのGCDが1となるものが存在しないようにしたい。
A[i]の約数xを選び、A[i]をxで割ることをコストxで行えるとする。
条件を満たす最小コストを求めよ。

解法

この問題は以下のように言い換えられる。
|A|個の点と、1～100000(max(A))に対応する点からなる二部グラフを考える。
A[i]を素因数分解したときp^qを約数に持つ場合、前者のi番の点と、後者のp番の点に間に、コストp*qの辺を張ろう

このグラフが閉路を含まないようにすればよい。
よって、最大全域木を求め、削除した辺の総コストを答えればよい。

int N;
int A[202020];
vector<pair<int,pair<int,int>>> V;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<2<<20> uf;

const int prime_max = 1010101;
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;
	
	while(divp[n]>1) {
		V[divp[n]]++;
		n/=divp[n];
	}
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		auto m=enumpr(x);
		FORR2(a,b,m) {
			V.push_back({a*b,{i,202020+a}});
		}
	}
	sort(ALL(V));
	reverse(ALL(V));
	ll ret=0;
	FORR2(c,p,V) {
		if(uf[p.first]==uf[p.second]) {
			ret+=c;
		}
		else {
			uf(p.first,p.second);
		}
	}
	cout<<ret<<endl;
}

まとめ

解法は割とシンプル。