题目：

给出任意$n$个数字（放在数组$A$中），然后找到任意个数字使得这任意个数字的和是$n$的倍数

题目提供spj. 只需输出一组符合条件的答案即可。

输出的时候，第一行输出当前方案的总个数，之后输出方案里面的数字。

样例:

输入

8
2
5
6
3
18
7
11
19

输出

2
2
6

说明：

$2 \leqslant n \leqslant 50000 $

$0 < A[i] \leqslant 10^9$

如果没有找到符合条件的答案，输出No Solution

方法：

哈哈哈哈哈，这个题一定有解。

如果才用暴力算法，则一共要判断$C_n^{1} + C_n^{2} + \cdot \cdot \cdot +C_n^{n} = 2^n - 1$种情况，肯定会超时
$$ (1 + 1) ^ n = C_n^{0}\cdot1^n\cdot1^0 + C_n^{1}\cdot1^{n-1}\cdot1^{1}+\cdot\cdot\cdot+C_n^{n-1}\cdot1^1\cdot1^{n-1} + C_n^{n}\cdot1^0\cdot1^n$$
$$= C_n^{0}+ C_n^{1} + C_n^{2} + \cdot \cdot \cdot +C_n^{n} = 2^n$$
$$C_n^{1} + C_n^{2} + \cdot \cdot \cdot +C_n^{n} = 2^n - 1 $$

所以这个题需要换一种姿势来解决：前缀和

记$Sum[i] = A[1] + A[2] + \cdot \cdot \cdot+A[i]$

对所有$Sum[i] = S[i] \% n$，则此时$0\leqslant Sum[i]\leqslant n - 1$

如果出现某一个$Sum[i] = 0$,则说明当前数组 $A[1] + A[2] + \cdot\cdot\cdot + A[i] $是$n$的倍数，直接输出前$i$个数字

如果所有的$Sum[i]$都不为0,然后根据_鸽巢原理_，$n$个位置放$n-1$个数字，一定会出现重复的。

即一定存在$Sum[x] == sum[y], x \neq y$

我们只需找到当前的$x$和$y$即可。

这里的代码是一个小技巧：

int vis[n] // 记录当前  sum[i]第一个出现的位置是多少。 最开始都为0。
for(int i = 1; i <= n; ++ i){
    if(vis[sum[i]]){
        printf("%d\n", i - vis[sum[i]]);
        for(int j = vis[sum[i]] + 1; j <= i; ++ j){
            printf("%d\n", a[j]);
        }
        return 0;
    }
    vis[sum[i]] = i;
}

代码：

#include <cstdio>
#include <cstring>
const int N = 50000 + 10;
int a[N], sum[N];
int vis[N];
int main(){
    int n;
    scanf("%d", &n);
    sum[0] = 0;
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        sum[i] = (sum[i - 1] + a[i]) % n;
        if(sum[i] == 0){
            printf("%d\n", i);
            for(int j = 1; j <= i; ++ j){
                printf("%d\n", a[j]);
            }
            return 0;
        }
    }

    memset(vis, 0, sizeof vis);
    // 此时 n个数中 一定有两个重复的 找到重复的即为res
    for(int i = 1; i <= n; ++ i){
        if(vis[sum[i]]){
            printf("%d\n", i - vis[sum[i]]);
            for(int j = vis[sum[i]] + 1; j <= i; ++ j){
                printf("%d\n", a[j]);
            }
            return 0;
        }
        vis[sum[i]] = i;
    }
    return 0;
}