Codeforces #196 Div1. C. Divisor Tree

これはCだけど何とか自力で解けた。
http://codeforces.com/contest/338/problem/C

問題

以下のような根付き木を考える。

• 各頂点は自然数を持つ。
• 各頂点の値は、子の値の積である。
• 葉となる頂点の値は素数である。

ここで、N要素の数列A[i]が与えられる。
A[i]のすべてを含む根付き木のうち、頂点数を最少化し、その数を答えよ。

解法

頂点を減らしたいので、A[i]を分割してA[i]に含まれない合成数を作る必要はない。
その場合はA[i]を素因数分解して葉となる頂点を作ればよい。

よって、ソート済みのAについて、できるたけi

int N;
ll A[10],B[10];
int pr[10];
int tar[10];

int NP,prime[100000];
const int prime_max = 1000000;
void cprime() {
	static int p[prime_max];
	int i,j;
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[NP++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=i;
	}
}

int calc() {
	int i,x,nt=0,r=N;
	FOR(i,N) if(tar[i]==i) nt++;
	if(nt>1) r++; // A[N-1] is not root

	FOR(i,N) {
		if(B[i]==1) continue;
		ll xx=B[i];
		FOR(x,NP) {
			if(xx<prime[x]) break;
			while(xx%prime[x]==0) r++,xx/=prime[x];
		}
		if(xx>1) r++;
		if(A[i]==B[i] && pr[i]==1) r--;
	}
	return r;
}

int dfs(int cur) {
	ll t;
	if(cur==N) return calc();
	// cur
	tar[cur]=cur;
	int r=dfs(cur+1);
	
	for(tar[cur]=cur+1;tar[cur]<N;tar[cur]++) {
		if(B[tar[cur]] % A[cur]==0) {
			B[tar[cur]] /= A[cur];
			r=min(r,dfs(cur+1));
			B[tar[cur]] *= A[cur];
		}
	}
	return r;
}

void solve() {
	int f,i,j,k,l, x,y;
	ll ret=0;
	
	cprime();
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N) {
		ll xx=B[i]=A[i];
		FOR(x,NP) while(xx%prime[x]==0) pr[i]++,xx/=prime[x];
		if(xx>1) pr[i]++;
	}
	
	_P("%d\n",dfs(0));
	
}

まとめ

こういう数学系問題をぱっとひらめくことができたのはよかった。