Codeforces #257 Div1 C. Jzzhu and Apples

Codeforcesお得意のconstructionゲー。
http://codeforces.com/contest/449/problem/C

問題

正の整数Nが与えられる。
1～Nの数字が1個ずつ与えられるので、それらを2つずつペアにしていく。
その際、ペアの数値は1より大きな公約数を持たなければならない。

ペアの数を最大化せよ。

解法

いろんな解法がありそうだが、回答を見て一番シンプルなものをここでは紹介。
1及びN/2以上の素数は明らかにペアになる数字がないので、それ以外をペアにすることを考える。

まず2以上の数を最小の素因数でグループ化する。
3以上の数pを素因数とする各グループは、当然pを公約数とできるのでそれらを大きな順にペアにしていく。
グループ内の数が奇数だと、最後にp自体が残るので、その値がN/2以下であれば2pとペアにする。
最後に、2を素因数とするグループだけが残るので2個ずつペアにすればよい。

int N;
const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
vector<int> E[100001];
vector<pair<int,int> > V;
int vis2[100001];

void cprime() {
	int i,j;
	for(i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(j=i;j<prime_max;j+=i) divp[j]=i;
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	
	cprime();
	for(i=2;i<=N;i++) if(i%2) E[divp[i]].push_back(i);
	
	for(i=3;i<=N;i++) if(E[i].size()) {
		for(j=0;j+1<E[i].size();j+=2) V.push_back(make_pair(E[i][E[i].size()-j-1],E[i][E[i].size()-j-2]));
		if(E[i].size()%2 && 2*i<=N) V.push_back(make_pair(i,2*i)),vis2[i*2]=1;
	}
	for(i=2;i<=N;i++) if(i%2==0 && vis2[i]==0) E[2].push_back(i);
	for(j=0;j+1<E[2].size();j+=2) V.push_back(make_pair(E[2][j],E[2][j+1]));
	cout << V.size() << endl;
	ITR(it,V) cout << it->first << " "  << it->second << endl;
	
}

まとめ

こういわれると割とあっさりだけど、本番に思いつける気しない…。