题意:

　　给出一个长度为n(n<=10^5)的数组a,  数组a是数字1到n的一种排列(打乱顺序).

　　每次可以选择两个数(不同)进行交换,　但是交换的条件是被选择的两个数的下标之差加1应该是一个素数.

思路:

　　比赛的时候WA到爆..好弱, 思路基本都是对的, 贪心. 用数组pos[i]来维护值i在数组中的位置.

　　对于第i个数, 如果 pos[i]-i+1是素数,那么就直接交换.否则, 需要多次交换来使得a[i] = i;

　　采用贪心策略, 从i+1开始枚举是否可以与pos[i]进行交换, 这里交换的次数不会很多,

　　因为只有当m!+2, m!+3, ......., m!+m时会存在m-1个连续的合数, 而n<=10^5, 所以m <=8

　　所以交换的次数不会超过５次．

附上代码：

1 /************************************************************************* 2     > File Name: C.cpp 3     > Author: Stomach_ache 4     > Mail: sudaweitong@gmail.com 5     > Created Time: 2014年05月15日 星期四 23时51分15秒 6     > Propose:  7  ************************************************************************/ 8  9 #include 
     
      10 #include 
      
       11 #include 
       
        12 #include 
        
         13 #include 
         
          14 #include 
          
           15 #include 
           
            16 #include 
            
             17 using namespace std;18 19 bool is_prime[100005];20 int a[100005], pos[100005]; // hold the index of the value of i21 typedef pair
             
               pii;22 vector
              
                ans; // keep each move...23 24 void 25 init() {26 memset(is_prime, true, sizeof(is_prime));27 is_prime[1] = false;28 for (int i = 2; i < 1000; i++) {29 if (is_prime[i]) {30 for (int j = i*i; j < 100002; j += i) {31 is_prime[j] = false;32 }33 }34 }35 return ;36 }37 38 int39 main(void) {40 init();41 int n;42 scanf("%d", &n);43 for (int i = 1; i <= n; i++) {44 scanf("%d", a + i);45 pos[a[i]] = i;46 }47 for (int i = 1; i <= n; i++) {48 if (i == a[i]) continue;49 if (is_prime[pos[i]-i+1]) {50 swap(a[i], a[pos[i]]);51 ans.push_back(pii(pos[i], i));52 pos[a[pos[i]]] = pos[i];53 pos[i] = i;54 } else {55 // distance from index i to pos[i]56 int d = pos[i] - i;57 // in other words, a[i] will be equal to i when d equals 058 while (d) {59 for (int k = d; k >= 1; k--) {60 if (is_prime[k+1]) {61 // from index of i+d-k to index of pos[i]62 swap(a[i+d-k], a[pos[i]]);63 // push to ans64 ans.push_back(pii(i+d-k, pos[i]));65 // update pos[]66 pos[a[pos[i]]] = pos[i];67 pos[i] = i+d-k;68 // update d69 d -= k;70 break;71 }72 }73 }74 }75 }76 // for (int i = 1; i <= 10; i++) {77 // cout << a[i] << ' ';78 // }79 // cout << endl;80 int len = ans.size();81 printf("%d\n", len);82 for (int i = 0; i < len; i++) {83 if (ans[i].first > ans[i].second) {84 swap(ans[i].first, ans[i].second);85 }86 printf("%d %d\n", ans[i].first, ans[i].second);87 }88 89 return 0;90 }