自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:19:01，当前版本为作者最后更新于2020-03-18 19:09:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

upd：修改了一处笔误，感谢 TheShadow 指出。请管理重新审核。

$\text{Subtask}\;1$：看样例输出。

$\text{Subtask}\;2$：正常的爆搜应该能过。（当然你爆搜写的是假的（指正确性）就过不了）

$\text{Subtask}\;3$：爆搜找规律 数学推导。

我们来分情况讨论。

$n=4k+1$：取一个 $n$，$2k$ 个 $1$，$2k$ 个 $-1$ 即可。

$n=4k+2$：假设可以，设 $(a_1,a_2,\cdots,a_n)$ 是 $n$ 的一个「良好的分拆」。既然 $\prod a_i=4k+2$，那么 $a_1,a_2,\cdots,a_n$ 中必定恰好有一个偶数，再根据 $\sum a_i=4k+2$，可得 $4k+1$ 个奇数和一个偶数的和是偶数，不可能。故此时 $n$ 没有「良好的分拆」。

$n=4k+3$：假设可以，设 $(a_1,a_2,\cdots,a_n)$ 是 $n$ 的一个「良好的分拆」。既然 $\prod a_i=4k+3$，那么 $a_1,a_2,\cdots,a_n$ 中必定有奇数个 $4k+3$ 型数和偶数个 $4k+1$ 型数。无论是有 $4k+1$ 个 $4k+3$ 型数和 $4k+2$ 个 $4k+1$ 型数，还是有 $4k+3$ 个 $4k+3$ 型数和 $4k$ 个 $4k+1$ 型数，其和都不是 $4k+3$ 型数。故此时 $n$ 没有「良好的分拆」。

$n=4k$：要分类讨论。

• $n=4$：没有，读者自证不难（
• $n=8k$：一个 $4k$，一个 $2$，$6k-2$ 个 $1$，$2k$ 个 $-1$。
• $n=8k+4$：一个 $4k+2$，一个 $-2$，$6k+3$ 个 $1$，$2k-1$ 个 $-1$。

按照上面的方式构造即可。

（很好奇比赛的时候有没有人找规律找出来

$\texttt{code:}$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

void out(int n)
{
	if(n%4==1)
	{
		puts("YES");
		if(n==1) printf("1\n1 1\n");
		else printf("3\n1 %d\n%d 1\n%d -1\n",n,n/2,n/2);
	}
	else if(n%4==2) puts("NO");
	else if(n%4==3) puts("NO");
	else
	{
		if(n%8==0)
		{
			puts("YES");
			printf("4\n1 %d\n1 2\n%d 1\n%d -1\n",n/2,n-n/4-2,n/4);
		}
		else
		{
			if(n==4) puts("NO");
			else
			{
				puts("YES");
				printf("4\n1 %d\n1 -2\n%d -1\n%d 1\n",n/2,n/4-2,n-n/4);
			}
		}
	}
}
int main()
{
	int T=rd();
	while(T--) out(rd());
	return 0;
}