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

CodeForces 432C Prime Swaps

2024-07-06 12:51:20   223人阅读

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之类的数，而且都不相同，简单的循环一次，把每个数放在它应该放得位置，这样最终的次数就不会超过5n，为什么呢，我也不知道为什么啊，这个方法虽然想到了，可是自己也不知道，看别人的也是这样做，这个题还有一点就是，判断是否是prime时，不要每次都去判断，把500000以内的prime数记录一下，这样时间会得到很大的优化
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define  inf 0x0f0f0f0f

using namespace std;
const int maxn=100000+10;
bool vis[maxn];
void prime()
{
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    //c=0;
    for (long long i=2;i<=100000;i++)
    {
        if (!vis[i])
        {
            //prm[c++]=i;
            //cout<<i<<" ";
            if (i*i<100000){
                for (long long j=i*i;j<=100000;j+=i) vis[j]=1;}
        }
    }
}
int main()
{
    prime();
    int n,a[maxn],id[maxn];
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        id[a[i]]=i;
    }
    int x[maxn*5],y[maxn*5];
    int cut=0;
    for (int i=1;i<=n;i++)
    {
        while (id[i]!=i)
        {
            int j=i;
            while(vis[id[i]-j+1]!=0) j++;
            x[cut]=j; y[cut]=id[i];
            a[id[i]]=a[j];
            id[a[j]]=id[i];
            a[j]=i;
            id[i]=j;
            cut++;
        }
    }
    printf("%d\n",cut);
    for (int i=0;i<cut;i++)
    printf("%d %d\n",x[i],y[i]);
    return 0;
}

作者 chensunrise


联系
我们