Description

题目链接

题目大意:给定 $n$,构造一组序列 $\{a_n\}$ 满足 $\sum \limits_{i = 1}^n a_i = 0, \prod \limits_{i = 1}^n a_i = n$。

Solution

这种题不打表是怎么做出来的???

结论:当且仅当 $n \bmod 4 = 0$ 时有解。

首先证明 $n \bmod 2 = 0$。若 $n \bmod 2 = 1$,则根据 $\prod \limits_{i = 1}^n a_i = n$,有 $a_i \bmod 2 = 1$。不难发现此时 $\sum \limits_{i = 1}^n a_i \ne 0$,故 $n \bmod 2 = 0$。

再证 $n \bmod 4 = 0$,此时必须满足序列中有至少两个偶数。若只有一个偶数,根据上文 $n$ 是偶数的结论,此时 $\sum \limits_{i = 1}^n a_i$ 为奇数,故 $n \bmod 4 = 0$。

接下来给出构造方法:设 $n = 4k$,则当 $k \bmod 2 = 0$ 时,序列为 $\{-2, -2k, 1, 1, \cdots, 1, -1, -1, \cdots -1, -1\}$。当 $k \bmod 2 = 1$ 时,序列为 $\{2, -2k, 1, 1, \cdots, 1, -1, -1, \cdots -1, -1\}$。

这种题是怎么想出来的,不懂。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int T, n;

int main() {
    read(T);
    while (T--) {
        read(n);
        if (n % 4) {
            puts("w33zAKIOI");
            continue;
        }
        int k = n / 4;
        if (k % 2) {
            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 ");
        }
        puts("");
    }
    return 0;
}
Last modification:September 2nd, 2021 at 02:16 am