yukicoder : No.1917 LCMST

これは自力で解けた。
https://yukicoder.me/problems/no/1917

問題

N頂点の完全グラフを考える。
正整数列Aが与えられる。
頂点iとjを結ぶ辺のコストをLCM(A[i],A[j])とするとき、最小全域木の構築コストを求めよ。

解法

A[i]=A[j]であるような頂点は、コストA[i]で互いに結ぶのがベスト。
よって、残りはA[i]が異なる頂点同士をどう結ぶかという問題になる。

正整数dを1～10^5まで走査し、以下を行う。
A[i]がdの倍数のものを列挙し、うち最小の値を持つ頂点に、他の頂点との間に辺を結ぶものとし、最小全域木を成す辺の候補を作る。

辺の候補の総数は高々O(NlogN)個である。
あとはこの辺の候補に対しクラスカル法でMSTを作ればよい。

int N;
int C[1010101];

ll mi[101010];
ll base[101010];
int cand[101010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	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<101010> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		if(C[x]) ret+=x;
		else C[x]=1;
	}
	
	vector<pair<ll,ll>> V;
	for(i=1;i<=100000;i++) {
		for(j=i;j<=100000;j+=i) if(C[j]) {
			if(cand[i]) {
				V.push_back({1LL*cand[i]*j/i,(1LL*cand[i]<<32)|j});
			}
			else {
				cand[i]=j;
			}
		}
	}
	
	sort(ALL(V));
	FORR2(co,e,V) {
		x=e%(1LL<<32);
		y=e>>32;
		if(uf[x]!=uf[y]) {
			ret+=co;
			uf(x,y);
		}
	}
	
	
	cout<<ret<<endl;
	
}

まとめ

本番もっと面倒な解法を取ってしまった。