【题意】:给出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