POJ 3370 Halloween Treats 解題：抽屜原理與前綴和取模

題目大意

c 個孩子，n 個鄰居 (c ≤ n)。第 i 個鄰居給 a[i] 顆糖。選擇一個非空子集，使糖果總數能被 c 整除 (孩子們平分)。輸出選擇的鄰居編號 (1-based)。

抽屜原理證明

考慮前綴和 S[k] = Σ_{i=1}^k a[i] 對 c 取模。共有 n+1 個前綴和 (含 S[0]=0) 但只有 c 種餘數 (0..c-1)。因 n ≥ c，由鴿巢原理必存在 i < j 使 S[i] % c == S[j] % c。則區間 [i+1, j] 的和為 c 的倍數。

演算法

1. 計算前綴和模 c，記錄每個餘數首次出現的位置 pos[rem] (初始 pos[0]=0)。
2. 遍歷 k=1..n，若 pos[S[k]%c] 已存在 (≠ -1)，則區間 [pos[rem]+1, k] 為解，輸出並結束。
3. 否則記錄 pos[S[k]%c] = k。

程式碼

int main() {
    int c, n;
    while (cin>>c>>n, c||n) {
        vector a(n+1);
        for (int i=1;i<=n;++i) cin>>a[i];
        vector pos(c, -1);
        pos[0] = 0;
        int sum = 0;
        for (int i=1;i<=n;++i) {
            sum = (sum + a[i]) % c;
            if (pos[sum] != -1) {
                for (int j=pos[sum]+1;j<=i;++j) {
                    cout<