P8103

猫猬兽 · 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;
}