POJ 2356 Find a Multiple：鴿籠原理必有解

POJ 2356 Find a Multiple：鴿籠原理必有解

給 N (≤ 10000) 個正整數（每個 ≤ 15000），找非空子集使和為 N 的倍數。鴿籠原理保證必有解。

鴿籠原理證明

前綴和 sum[i] = (a[1]+...+a[i]) % N，共 N 個值，取值 [0, N-1]。

• 若某 sum[i] == 0，前 i 個數即為解。
• 否則 N 個值落入 N-1 個非零餘數，必有 i < j 使 sum[i] == sum[j]。區間 (i, j] 的和模 N 為 0。

算法流程

1. 計算前綴和模 N。
2. 記錄每個餘數首次出現位置 pos[rem]，pos[0]=0。
3. 遍歷 i=1..N，若 pos[sum[i]] 已存在，輸出區間 (pos[sum[i]], i]。

完整代碼（C++）

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

int n, a[MAXN], sum[MAXN], pos[MAXN];

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++) sum[i] = (sum[i-1] + a[i]) % n;
        memset(pos, -1, sizeof(pos));
        pos[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (pos[sum[i]] == -1) pos[sum[i]] = i;
            else {
                int cnt = i - pos[sum[i]];
                printf("%d\n", cnt);
                for (int j = pos[sum[i]] + 1; j <= i; j++) printf("%d\n", a[j]);
                break;
            }
        }
    }
    return 0;
}

關鍵細節

• 輸出格式：第一行元素個數，隨後每行一個元素值（非下標）。
• 題目保證有解，無需處理無解情況。
• 數組大小 MAXN=100010 足夠。

暴力解法（不可行）

雙重循環枚舉所有區間 O(N²)，N=10000 會 TLE。鴿籠原理將問題降維為 O(N) 線性掃描。

鴿籠原理通俗版

「N 個抽屜放 N+1 隻鴿子（含 sum[0]=0），至少一個抽屜 ≥ 2 隻。」本題中抽屜是餘數 0..N-1，鴿子是前綴和。

複雜度

• 時間：O(N)。
• 空間：O(N)。

POJ 2356 是鴿籠原理在「子集和取模」問題中應用的教科書級範例，代碼極短、邏輯鐵clad，是競賽程序員必背模板之一。