Codeforces #246 Div2 C. Prime Swaps

Div2回なのにC,EでミスとDの解き方がわからず、まさかのAB正答のみ。
rate対象外で良かった…。
http://codeforces.com/contest/432/problem/C

問題

1～Nのpermutationである数列A[i]が与えられるので、これを昇順に並べ替えたい。
i<jであるA[i]とA[j]は、j-i+1が素数ならswap出来る。

5N回以内のswapでA[i]を昇順に並べ替える手順を答えよ。

解法

昇順ということはA[i]にはi+1を入れたい。
i+1がj > iであるA[j]に入っている場合、それをA[i]に移動することを考える。

ゴールドバッハ予想より、2以上の数字は恐らく３個以下の素数の和で表せる。
よって、(j-i+1)は３つ以下の素数の和で表せるため、そのような素数を求め、swapして目的地に移動すればよい。

事前にエラトステネスの篩でN以下の素数を列挙できているとする。
移動手順の選択方法は以下のようにすればよい。

• (j-i+1)が素数なら１手で移動すればよい。
• (j-i+1)が偶数なら、ゴールドバッハ予想より２手で移動できるはずである。(j-i+1)以下の各素数pに対し、(j-i+1)-pも素数か判定すればよい。
• (j-i+1)が奇数なら、初手で３移動すれば(j-i-1)が偶数になるので、あと２手で移動できる。

int N;
int A[100001],B[100001];
int step[100005];
int NP,prime[100000];
const int prime_max = 1000000;
int p[prime_max];
void cprime() {
	
	int i,j;
	NP=0;
	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;
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cprime();
	for(i=2;i<=100003;i++) {
		if(p[i]==0) step[i]=i;
		else if(i%2) step[i]=3;
		else {
			for(y=0;y<NP;y++) {
				if(p[i-prime[y]]==0) {
					step[i]=i-prime[y];
					break;
				}
			}
		}
	}
	
	vector<pair<int,int> > V;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A[i]=x-1;
		B[x-1]=i;
	}
	FOR(i,N) {
		while(A[i]!=i) {
			
			x=step[B[i]-i+1]-1;
			y=B[i]-x;
			V.push_back(make_pair(y,B[i]));
			swap(A[y],A[B[i]]);
			B[A[B[i]]]=B[i];
			B[A[y]]=y;
		}
	}
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%d %d\n",V[i].first+1,V[i].second+1);
}

まとめ

Div2C/Div1A相当にしては面倒な問題。