题目链接:http://codeforces.com/contest/432/problem/C
首先由题意分析出:这些数是从1到n且各不相同,所以最后结果肯定是第i位的数就是i。
采用这样一种贪心策略:从1到n枚举每一位。如果第i位不是i,那么就把i 从它所在的位置移动到第i 位,每次移动的距离要选取符合要求的最大的素数,那么由哥德巴赫猜想可以知道,最后肯定小于5次移动就移好了。每一位都这么移就行了。这过程中记录一下每次谁和谁交换位置就行了。
我把x[],y[]开成了maxn而导致了RE,改成5*maxn就过了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
#define maxn 100010
int n,notpr[maxn];
int a[maxn],id[maxn],k=,x[maxn*],y[maxn*];
int main()
{
//freopen("in7.txt","r",stdin);
//freopen("out.txt","w",stdout);
memset(notpr,,sizeof(notpr));
int m=sqrt(maxn);
for(int i=;i<m;i++)
{
if(!notpr[i])
{
for(int j=i*i;j<=maxn;j+=i)
{
notpr[j]=;
}
}
}
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
id[a[i]]=i;
}
for(int i=;i<=n;i++)
{
while(id[i]!=i)
{
int j=i;
while(notpr[id[i]-j+]) j++;
x[k]=j;
y[k]=id[i];
k++;
int t=a[j];
swap(a[id[i]],a[j]);
swap(id[i],id[t]);
}
}
printf("%d\n",k);
for(int i=;i<k;i++)
{
printf("%d %d\n",x[i],y[i]);
}
//fclose(stdin);
//fclose(stdout);
return ;
}