組合數(shù)學(xué)問(wèn)題
處理之前先對(duì)整個(gè)隊(duì)列求一個(gè)和；
然后對(duì)每一個(gè)部分和統(tǒng)計(jì)一下
1
#include <stdio.h>
2#include <string.h>
3
4int seq[100100];
5int md[6000];
6
7
long long jx(long long x) 
{
8
return x*(x+1)/2;
9
}
10int main() {
11 int n, l, u;
12 int i;
13 int sum, m;
14 long long res, now, best;
15
16
while(scanf("%d%d%d", &n, &l, &u)!=EOF) {
17 for(i=0; i<n; i++) {
18 scanf("%d", &seq[i]);
19
}
20 best = (long long)-1;
21 for(m=l; m<=u; m++) {
22 memset(md, 0, sizeof(md));
23 md[0] = 1;
24 sum = 0;
25 for(i=0; i<n; i++) {
26 sum = (sum+seq[i])%m;
27 md[sum] ++;
28 }
29 now = 0;
30 for(i=0; i<m; i++) {
31 now += jx((long long)(md[i]-1));
32 }
33 //printf("%d: %I64d\n", m, now);
34 if(now > best) {
35 best = now;
36 res = m;
37 }
38 }
39 printf("%d\n", res);
40 }
41 return 0;
42}
43
44