P7567 「MCOI-05」魔仙 题解

· · 题解

题目传送门

这题我在比赛中推了30min才推出来结果发现是原题。。。

菜是原罪

先证一下n是4的倍数：

设这n个整数分别为a_1,a_2...a_n，则a_1\times a_2\times ...\times a_n=n，a_1+a_2+...+a_n=0

1.数列中有0个偶数：

则n为n个奇数之积，故也为奇数

所以a_1+a_2+...+a_n为奇数个奇数之和，必为奇数

与a_1+a_2+...+a_n=0矛盾

2.数列中有1个偶数：

则n为n-1个奇数与1个偶数之积，故为偶数

所以n-1为奇数

所以a_1+a_2+...+a_n为奇数个奇数之和再加一个偶数，必为奇数

再次与a_1+a_2+...+a_n=0矛盾

3.数列中有2个偶数：

则n为n-2个奇数与2个偶数之积，故为偶数

所以n-2为偶数

所以a_1+a_2+...+a_n为偶数个奇数之和再加两个偶数，必为偶数

不与a_1+a_2+...+a_n=0矛盾

因此，此序列中至少有2个偶数，即n能被4整除

再来看看怎么求出数列：

因为n为4的倍数，所以设n=4k（k为正整数）

1.当k为奇数时：

n=2\times (-2k)\times 1^{3k-2}\times (-1)^k

验证：

(1).和：

2-2k+3k-2-k=0

(2).积：

2\times (-2k)\times 1^{3k-2}\times (-1)^k =-4k\times 1\times -1 =4k=n

2.当k为偶数时：

n=(-2)\times (-2k)\times 1^{3k}\times (-1)^{k-2}

验证：

(1).和：

-2-2k+3k-k+2=0

(2).积：

(-2)\times (-2k)\times 1^{3k}\times (-1)^{k-2} =4k\times 1\times 1 =4k=n

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        if(n%4==0){
            int k=n/4;
            if(k%2==1){
                printf("2 -%d ",k*2);
                for(int i=1;i<=3*k-2;i++){
                    printf("1 ");
                }
                for(int i=1;i<=k;i++){
                    printf("-1 ");
                }
            }else{
                printf("-2 -%d ",k*2);
                for(int i=1;i<=3*k;i++){
                    printf("1 ");
                }
                for(int i=1;i<=k-2;i++){
                    printf("-1 ");
                }
            }
            printf("\n");
        }else{
            printf("w33zAKIOI\n");
        }
    }
    return 0;
}
//w33z AK IOI!