POJ 2356 Find a multiple(鸽巢原理)

题目链接

题目大意

  给n个数找出其中任意几个数使其和能被n整除。

解题思路

  对n取模的结果是0~n-1，有n个数，显然是有解的，直接利用前缀和来求解符合条件的区间即可。

代码

const int maxn = 1e6+10;
const int maxm = 2e2+10;
int arr[maxn], sum[maxn], pos[maxn]; int n, l, r;
int main() {
    cin >> n; 
    for (int i = 1; i<=n; ++i) {
        cin >> arr[i];
        sum[i] += arr[i]+sum[i-1];
        sum[i] %= n;
        if (pos[sum[i]] || !sum[i]) l = pos[sum[i]]+1, r = i;
        pos[sum[i]] = i;
    }
    cout << r-l+1 << endl;
    for (int i = l; i<=r; ++i) cout << arr[i] << endl;
    return 0;
}