首先了解到鸽巢原理: 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。
可以推出一个结论:任意n+1个数,必有一段连续的数字之和是n的倍数。
先预处理出一个前缀和,假设到i时,前缀和也模n不为0,要加上的第i+1个数模n也不为0(为0那么答案为这个数),于是容易得出到i+1时的前缀和模n的结果必定与为i时的结果不相同。如果到j时的前缀和模n与到i时相同,那么从i+1到j的所有数的和必为n的倍数。显然是存在这样的解,因为模n的结果最多只有n个,其中为0时又正好是解。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn = 1e5 + 10; int s[maxn], tag[maxn], id[maxn]; bool rema[maxn]; bool cmp(int a, int b) { return s[a] < s[b]; } int main() { // freopen("A.in", "r", stdin); int c, n, sum; while(~scanf("%d%d", &c, &n) && c) { bool flag = false; for(int i = 0; i < n; i++) { scanf("%d", &s[i]); id[i] = i; } // sort(id, id + n, cmp); sum = 0; memset(rema, false, sizeof(rema)); rema[0] = true, tag[0] = -1; for(int i = 0; i < n; i++) { sum += s[id[i]]; sum %= c; if(rema[sum]) { printf("%d", id[tag[sum] + 1] + 1); for(int j = tag[sum] + 2; j <= i; j++) printf(" %d", id[j] + 1); printf("\n"); flag = true; break; } rema[sum] = true; tag[sum] = i; } if(flag) continue; // else // printf("no sweets\n"); } return 0; }