POJ 2356 Find a Multiple：鴿巢原理構造 N 的倍數子集

問題大意

給定 N ≤ 10000 個正整數（每個 ≤ 15000），選出非空子集使其和為 N 的倍數。保證有解。

鴿巢原理證明有解

考慮前綴和 S[i] = a[0] + ... + a[i] (0 ≤ i < N)。共 N 個前綴和，對 N 取模餘數只能是 0..N-1（共 N 種）。

• 若某 S[i] % N == 0，則 [0..i] 即為答案
• 否則 N 個餘數落入 N-1 個非零抽屜，必有 S[j] % N == S[i] % N (j > i)，則 (S[j] - S[i]) % N == 0，即 [i+1..j] 和為 N 的倍數

O(N) 構造算法

1. 計算前綴和並記錄每個餘數首次出現的索引 mod[r] = i
2. 若遇到 mod[r] != -1，輸出 [mod[r]+1 .. i]
3. 若某前綴和直接模 0，輸出 [0 .. i]

C++ 代碼

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10010;

int a[MAXN], mod[MAXN];
long long sum[MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        memset(mod, -1, sizeof(mod));
        for (int i=0; i