第二十二届SCU程序设计竞赛(Tencent CUP)

Problem A. 配对质数

此题事先把素数筛出来，由于从前往后可能会导致后面的数字无法配对，我们只需从后往前，把数x/2得到的两个数，即可完成配对操作

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;

template <typename T>
inline void read(T &x)
{
    T f = 1;
    x = 0;
    char ch = getchar();
    while (0 == isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (0 != isdigit(ch))
        x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    x *= f;
}
 
template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        x = ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int n;
int primes[4100100],cnt,vis[2000100],a[2000100],b[2000100],q;
bool st[4100100];
void init()
{
	st[1]=true;
	for(int i=2;i<=4100000;i++)
	{
		if(!st[i]) primes[++cnt]=i;
		for(int j=1;primes[j]*i<=4100000;j++) 
		{
			st[primes[j]*i]=true;
			if(i%primes[j]==0) break;
		}
	}
}
void solve()
{
	int flag=1;
//	vpii vec;
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		vis[i]=0;
	}
	int p=lower_bound(primes+1,primes+cnt+1,4*n-1)-primes;
	q=1;
	for(int i=2*n;i>=1;i--)
	{
		if(vis[i]) continue;
		int j=primes[p]-i;
		while(j<1||j>=i||vis[j])
		{
			p--;
			if(p<1) break;
			j=primes[p]-i;
		}
		if(p<1)
		{
			flag=0;
			break;
		}
		a[q]=i;
		b[q++]=j;
		vis[i]=vis[j]=1;
	}
	if(!flag) printf("-1\n");
	else
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d %d\n",a[i],b[i]);
		}
	}
}
int main()
{
	init();
	int _=1;
	scanf("%d",&_);
	while(_--)
	{
		solve();
	}
	return 0;
}