poj 2356 Find a multiple

题目意思

给你一个正整数N(N<10000)，随后给出N个正整数，从这N个数中选任意个数字，要求任意个数字的和能整除N，先输出数字个数，然后按任意序列输出所有数字。

Sample Input
5
1
2
3
4
1
Sample Output
2
2
3

思路分析

求序列的前缀和（并对N取模），当发现两个相等的前缀和时（s[i]%n==s[j]%n），即可判断，sum[k] k from i+1 to j，可以整除N，包括s[0]=0，共有n+1个前缀和，因为前缀和都是小于N的，所以一定存在前缀和相等的两项。（抽屉定理）

#include <iostream>
#include <map>
using namespace std;
int a[10005], sum[10005];
map<int, int>m;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    m[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        sum[i] %= n;
        if (m[sum[i]] == 0 && sum[i] != 0)
            m[sum[i]] = i;
        else
        {
            printf("%d\n", i - m[sum[i]]);
            for (int j = m[sum[i]] + 1; j <= i; j++)
                printf("%d%c", a[j], '\n');
            return 0;
        }
    }
}