自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:30:32，当前版本为作者最后更新于2021-04-12 21:06:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

小学数学经典题。小学曾在多个 MO 课听过做法。可是赛时由于设备原因写代码太麻烦了不想写，否则应该可以首 A（

首先，我们发现 $a-b$ 与 $a+b$ 奇偶性相同，即 $\sum\limits_{i=1}^{n}(a_i-b_i) \equiv \sum\limits_{i=1}^{n}(a_i+b_i) \pmod{2}$。

上式左边是 $\dfrac{n(n+1)}{2}$，右边是 $\dfrac{2n(2n+1)}{2}$。推一推发现需要 $n \equiv 0,1 \pmod{4}$。

然后感觉这个问题不是很好处理，联想到有解条件是 $n \equiv 0,1 \pmod{4}$，并且差取遍 $1 \sim n$，想到小学时很喜欢的一个问题：

把 $1$ 至 $n$ 各两个排成一列，使两个 $i$ 之间隔 $i$ 个数。

当时脑抽以为这个问题有解条件也是 $n \equiv 0,1 \pmod{4}$，推了下小情况发现是 $n \equiv 0,-1 \pmod{4}$（

但是发现如果把 $i$ 变成 $i+1$ 再加两个相邻的 $1$，正好变成两个 $i$ 的下标差 $i$，并且有解条件是 $n \equiv 0,1 \pmod{4}$。于是我就做出来了？

回忆了一下以前讲的构造，记得我特别喜欢它的原因是除了几个数外都是两个 $x+2$ 套着两个 $x$ 的形式。搞了一下搞出来了。

然后发现我的构造和 std 一模一样。。。大概就是这题引申过来的吧（

Code:

#include<cstdio>
#define rg register
int n;
int ans[2][1000003];
int main()
{
	scanf(" %d",&n);
	if(n&2)return 0&puts("-1 0");
	int m=n>>2;
	if(n&1)
	{
		ans[0][1]=1,ans[1][1]=2;
		ans[0][n]=n,ans[1][n]=n<<1;
		ans[0][n-2]=m+2,ans[1][n-2]=n+m;
		ans[0][n>>1]=n+(n>>1),ans[1][n>>1]=m<<3|1;
		ans[0][n-1]=(m+1)<<1,ans[1][n-1]=n+(m<<1|1);
		for(rg int i=1;i<m;++i)
		{
			ans[0][n-((i+1)<<1)]=2+i,ans[1][n-((i+1)<<1)]=n-i;
			ans[0][i<<1]=((m+1)<<1)-i,ans[1][i<<1]=((m+1)<<1)+i;
			ans[0][n-(i<<1|1)]=n+i,ans[1][n-(i<<1|1)]=(m<<3|1)-i;
			ans[0][i<<1|1]=n+(m<<1)-i,ans[1][i<<1|1]=n+(m<<1|1)+i;
		}
	}
	else
	{
		ans[0][1]=1,ans[1][1]=2;
		ans[0][n-1]=m+2,ans[1][n-1]=n+m+1;
		ans[0][n>>1]=n|1,ans[1][n>>1]=n+(m<<1|1);
		ans[0][n]=(m+1)<<1,ans[1][n]=n+((m+1)<<1);
		for(rg int i=1;i<m;++i)
		{
			ans[0][n-(i<<1|1)]=2+i,ans[1][n-(i<<1|1)]=n-i+1;
			ans[0][n-(i<<1)]=n+i+1,ans[1][n-(i<<1)]=(n<<1|1)-i;
			ans[0][i<<1]=((m+1)<<1)-i,ans[1][i<<1]=((m+1)<<1)+i;
			ans[0][i<<1|1]=n+(m<<1|1)-i,ans[1][i<<1|1]=n+((m+1)<<1)+i;
		}
	}
	for(rg int i=1;i<=n;++i)printf("%d %d\n",ans[1][i],ans[0][i]);
	return 0;
}