每年萬聖節都會出現同樣的問題：每位鄰居願意給出的糖果總數固定，無論有多少孩子上門，晚到的孩子可能一顆糖也拿不到。為了避免衝突，孩子們決定把所有糖果集中起來，再平均分配。根據去年的經驗，他們知道每位鄰居會給多少糖果。既然他們更在意公平而非糖果數量，他們想選擇一部分鄰居拜訪，使得分配時每個孩子得到的糖果數相同，且不能有剩餘糖果。你的任務是幫助孩子們找到一個解決方案。
輸入包含多組測試案例。每組測試案例的第一行包含兩個整數 c 和 n (1 ≤ c ≤ n ≤ 100000)，分別代表孩子數量和鄰居數量。下一行包含 n 個整數 a1 , ... , an (1 ≤ ai ≤ 100000)，其中 ai 表示拜訪第 i 位鄰居可獲得的糖果數。輸入以兩個零結束。
對於每組測試案例，輸出一行包含孩子們應選擇的鄰居索引（索引 i 對應給出 ai 顆糖果的第 i 位鄰居）。若不存在讓每個孩子至少分到一顆糖果的解，輸出 "no sweets"。若有多組解，輸出任意一組即可。
輸入： 4 5 1 2 3 7 5 3 6 7 11 2 5 13 17 0 0 輸出： 3 5 2 3 4
鴿巢原理（抽屜原理）是組合數學中的基本原理，包含四個基本形式：
定理：設 a₁, a₂, ..., aₘ 為正整數序列，則至少存在整數 k 和 l (1 ≤ k < l ≤ m)，使得 ak+1 + ak+2 + ... + al 是 m 的倍數。
證明：考慮前綴和 Sn = a₁ + a₂ + ... + an 對 m 取模的餘數。共有 m 個前綴和產生 m 個餘數，但餘數只有 0 到 m-1 共 m 種可能。根據鴿巢原理，至少有兩個前綴和的餘數相同，設為 Sk 和 Sl (k < l)，則 Sl - Sk = ak+1 + ... + al 必定是 m 的倍數。
本題中 m = c（孩子數），n = c（鄰居數，因為 c ≤ n），根據定理必定存在解。關鍵在於條件 c ≤ n，否則無法應用鴿巢原理。
使用前綴和取模 + 哈希表記錄首次出現的餘數位置：
#include <cstdio>
#include <cstdlib>
const int MAX_N = 100001;
int arr[MAX_N], modMap[MAX_N];
int main() {
int c, n;
arr[0] = modMap[0] = 0;
while (scanf("%d %d", &c, &n) != EOF && c) {
for (int i = 1; i <= n; i++) {
scanf("%d", arr+i);
modMap[i] = -1;
}
int lastMod = 0, curMod = 0, l = -1, r = -1;
for (int i = 1; i <= n; i++) {
curMod = (arr[i] + lastMod) % c;
if (modMap[curMod] != -1) {
l = modMap[curMod] + 1;
r = i;
break;
}
modMap[curMod] = i;
lastMod = curMod;
}
if (l != -1) {
while (l <= r) printf("%d ", l++);
putchar('\n');
} else puts("no sweets"); // 理論上必有解，此行可省略
}
return 0;
}
這道題目巧妙地將鴿巢原理應用於連續子數組和的問題，是數學思維在程式設計競賽中經典的應用案例。
