自动搬运

查看原文

来自洛谷，原作者为

	猫猬兽 **

搬运于2025-08-24 22:36:00，当前版本为作者最后更新于2022-02-07 14:22:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Part 1

判断可行性

我们先把所有数除以他们的最大公约数，考虑到答案一定是一个数翻倍得到的，所以此时如果所有数的和是 $2$ 的整数幂次，则有解，否则无解。

Part 2

构造方案

考虑到如果所有数的和大于 $1$，则必有偶数个奇数，将它们两两配对操作，则所有数都变为偶数。我们再把所有数除以他们的最大公约数，重复上述操作，直至序列中只剩下 $1$。

Part 3

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,i,t,k,a[100001],b,c,d,m,l[1000001],r[1000001];
int main()
{
	scanf("%lld",&t);
	for(k=1;k<=t;k=k+1)
	{
		scanf("%lld",&n);b=0;c=0;d=0;
		for(i=1;i<=n;i=i+1)
		{
			scanf("%lld",&a[i]);
			b=__gcd(b,a[i]);
		}
		for(i=1;i<=n;i=i+1)a[i]=a[i]/b;
		for(i=1;i<=n;i=i+1)c=c+a[i];
		for(i=1;;i=i*2)
		{
			if(i>c){d=1;break;}
			if(i==c)break;
		}
		if(d==1){printf("NO\n");continue;}
		else
		{
			printf("YES\n");m=0;
			while(1)
			{
				b=0;c=0;d=0;
				for(i=1;i<=n;i=i+1)
				{
					if(a[i]%2==1)
					{
						c=c+1;
						if(c==2)
						{
							m=m+1;c=0;
							if(a[i]>a[d]){l[m]=i;r[m]=d;a[i]=a[i]-a[d];a[d]=a[d]*2;}
							else {l[m]=d;r[m]=i;a[d]=a[d]-a[i];a[i]=a[i]*2;}
						}
						else d=i;
					}
				}
				if(c==1)break;
				for(i=1;i<=n;i=i+1)b=__gcd(b,a[i]);
				for(i=1;i<=n;i=i+1)a[i]=a[i]/b;
			}
			printf("%lld\n",m);
			for(i=1;i<=m;i=i+1)printf("%lld %lld\n",l[i],r[i]);
		}
	}
	return 0;
}