【题意】:给出n个数,问是否可以任意选出一些数使得其和是c的倍数。

【题解】:鸽巢原理

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 100500
22 int val[maxn];
23 int sum[maxn], idx[maxn];
24 int n, c;
25 
26 int getint(){
27     char c = getchar();
28     int t = 0;
29     while (c < '0' || c > '9') {
30         c = getchar();
31     }
32     while (c >= '0' && c <= '9') {
33         t = t * 10 + c - '0';
34         c = getchar();
35     }
36     return t;
37 }
38 
39 int main() {
40     while(~scanf("%d%d", &c, &n)) {
41         if(!c && !n) break;
42         sum[0] = 0;
43         int l, r;
44         for(int i = 0; i < maxn; i++) idx[i] = -1;
45         for(int i = 1; i <= n; i++) {
46             val[i] = getint();
47             sum[i] = (sum[i-1] + val[i]) % c;
48             if(idx[sum[i]] == -1) idx[sum[i]] = i;
49             else l = idx[sum[i]], r = i;
50         }
51         if(idx[0] != -1) {
52             for(int i = 1; i <= idx[0]; i++)
53                 printf("%d ", i);
54             printf("\n");
55         } else if(l != - 1) {
56             for(int i = l + 1; i <= r; i++) 
57                 printf("%d ", i);
58             printf("\n");
59         } else printf("no sweets\n");
60         
61     }
62     return 0;
63 }
64