N的倍数

Description

一个长度为$N$的数组$A$，从$A$中选出若干个数，使得这些数的和是$N$的倍数。
例如：$N = 8$，数组$A$包括：$2 5 6 3 18 7 11 19$，可以选$2 6$，因为$2 + 6 = 8$，是$8$的倍数。

Input

第$1$行：$1$个数$N$，$N$为数组的长度，同时也是要求的倍数。($2 \le N \le 50000$)
第$2 - N + 1$行：数组$A$的元素。($0 \lt A[i] \le 10^9$)

Output

如果没有符合条件的组合，输出$No \ Solution$。
第$1$行：$1$个数$S$表示你所选择的数的数量。
第$2 - S + 1$行：每行$1$个数，对应你所选择的数。

Input示例

8
2
5
6
3
18
7
11
19

Output示例

2
2
6

Solution

我们记$sum_i = \sum_{j = 1}^i{a_j}$，若对于某个$i$，$sum_i$为$n$的倍数，那么原序列的$[1, i]$即为答案。否则，对于$sum_i \ (1 \le i \le n)$这$n$个数，因为它们模$n$的余数在$[1, n - 1]$范围内，所以肯定存在$i,j \ (1 \le i \lt j \le n)$满足$sum_i % n = sum_j% n $，那么原序列的$[i + 1, j]$即为答案。

Standard

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

using namespace std;

const int N = 50010;

int n;
int a[N], app[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum = (sum + a[i]) % n;
        if (!sum) {
            printf("%d\n", i);
            for (int j = 1; j <= i; ++j)
                printf("%d\n", a[j]);
            return 0;
        }
        if (app[sum]) {
            printf("%d\n", i - app[sum]);
            for (int j = app[sum] + 1; j <= i; ++j)
                printf("%d\n", a[j]);
            return 0;
        }
        app[sum] = i;
    }
    puts("No Solution"); //tan 90°
    return 0;
}