首页 > 代码库 > CodeForces 432C Prime Swaps

CodeForces 432C Prime Swaps

2024-07-14 03:42:09   220人阅读

Description

You have an array a[1], a[2], ..., a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):

  • choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);
  • swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments: tmp = a[i], a[i] = a[j], a[j] = tmp (tmp is a temporary variable).

You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.

Input

The first line contains integer n(1 ≤ n ≤ 105). The next line contains n distinct integers a[1], a[2], ..., a[n](1 ≤ a[i] ≤ n).

Output

In the first line, print integer k(0 ≤ k ≤ 5n) — the number of used operations. Next, print the operations. Each operation must be printed as "ij" (1 ≤ i < j ≤ n; (j - i + 1) is a prime).

If there are multiple answers, you can print any of them.

Sample Input

Input
3
3 2 1
Output
1
1 3
Input
2
1 2
Output
0
Input
4
4 2 3 1
Output
3
2 4
1 2
2 4

题目大意：有n个数的序列，通过交换使其变得有序，交换的原则是每次交换的数字ai和aj，（j-i+1）必须是质数，要求在5n步内完成。
思路：很容易考虑到歌德巴赫猜想。该猜想虽未证明，不过科学家目前还未找出反例，在本题数据范围有限大的情况下是适用的。由猜想可得，每个大于等于5的数都可以有三个质数相加获得，而2,3都是质数，4=2+2,所以所有大于等于2的数都可以用质数表示。所以无论i，j多少，每次交换i，j都可以在三步之内获得。已知把一个无序数列变成有序数列最多需要交换n-1次，所以答案小于等于3（n-1），小于等于5n。
/* * Author:  Joshua * Created Time:  2014年07月20日 星期日 20时16分13秒 * File Name: c.cpp */#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define maxn 100005 int a[maxn],l[maxn<<2],r[maxn<<2];bool f[maxn];int n,ans;void primeNumber(){    memset(f,true,sizeof(f));    f[0]=f[1]=false;    for (int i=2;i<maxn;++i)        if (f[i])            for (int j=i+i;j<maxn;j+=i)                f[j]=false;}void change(int x,int y){    if (x==y) return;    if (x>y) swap(x,y);    for (int i=y;i>x;i--)        if (f[i-x+1])        {            swap(a[i],a[x]);            l[++ans]=x;            r[ans]=i;            change(i,y);            break;        }}void solve(){    ans=0;    for (int i=1;i<=n;++i)        scanf("%d",&a[i]);    for (int i=1;i<=n;++i)        while (a[i]!=i) change(i,a[i]);    printf("%d\n",ans);    for (int i=1;i<=ans;++i)        printf("%d %d\n",l[i],r[i]);}int main(){        primeNumber();    while (scanf("%d",&n)==1)        solve();    return 0;}

 


联系
我们