自动搬运

查看原文

来自洛谷，原作者为

	tallnut 楼头残梦五更钟，花底离愁三月雨

搬运于2025-08-24 23:12:27，当前版本为作者最后更新于2025-04-08 20:50:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我太菜了，一道绿题想不出来。还是 @zhikang 大神教我的。虽然他也看了官方题解。

首先锐评一下，这个构造题完全不同于正常的和出题人对脑电波的题，完全是个数学题，知道定理就一定会做，反之一定不会做。并且这个质数个数误导性也很强，差评。

思路

引理：伯特兰-切比雪夫定理：对于任意 $n\ge 2$ 且 $n$ 为正整数，在 $(n,n\times 2)$ 中必至少存在一个质数。

那么先把 $n\le 5$ 判掉，这个随便输出就行。令 $k=\lfloor\dfrac{n}{3}\rfloor$，根据定理，在 $(k,k\times 2)$ 中必存在一个质数，令该质数 $=x$。按照如下方式构造：

直到 $x-m\le 0$ 或 $x+m>n$ 为止。显然这些项全部 $=x$，为质数。剩下的项乱填。

因此此题结论可以加强成 $c_i$ 中至少存在 $2\times\lfloor\dfrac{n}{3}\rfloor$ 个质数。

代码

代码实现非常简单。AC 记录。

// NOTE: "[EDIT]" means you should edit this part by yourself
#include <bits/stdc++.h>
#define MULTITEST
using namespace std;
typedef long long ll;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e5 + 10;
int n,cnt,k,pos;
bool visited[N];
int ans[N];
bool prime(int x)
{
	for (int i = 2;i * i <= x;i++)
		if (x % i == 0)
			return false;
	return true;
}
void solve()
{
    cin >> n;
    if (n <= 5)
    {
    	rep1(i,1,n)
    		cout << i << ' ';
    	cout << '\n';
    	return;
	}
    k = n / 3;
    cl(visited);
    rep1(i,k,k * 2)
    {
    	if (prime(i))
    	{
    		pos = i;
    		break;
		}
	}
	cnt = 0;
	ans[++cnt] = pos;
	visited[pos] = true;
	rep1(i,1,min(pos - 1,n - pos))
	{
		ans[++cnt] = pos - i;
		ans[++cnt] = pos + i;
		visited[pos - i] = true;
		visited[pos + i] = true;
	}
	rep1(i,1,n)
		if (!visited[i])
			ans[++cnt] = i;
	rep1(i,1,n)
		cout << ans[i] << ' ';
	cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}