# [USACO16JAN]子共七Subsequences Summing to Sevens

Farmer John‘s NN

## 输入输出格式

The first line of input contains NN

lines each contain the NN

0…1,000,0000 \ldots 1,000,000

Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7. If no such group exists, output 0.

## 输入输出样例

7
3
5
1
6
2
14
10

5

## 说明

In this example, 5+1+6+2+14 = 28.

(a mod m) + (b mod m) ≡ a + b (mod m)
(a mod m) - (b mod m) ≡ a - b (mod m)
(a mod m) * (b mod m) ≡ a * b (mod m)

(pre[j] - pre[i ]) mod 7 = 0
=> pre[i] ≡ pre[j] (mod 7)

 1 //2018年2月14日14:15:25
2 #include <iostream>
3 #include <cstdio>
4 #include <cstring>
5 using namespace std;
6
7 const int N = 100001;
8 int n, a[N], sum[N], last[N], first[N], ans;
9
10 int main(){
11     scanf("%d", &n);
12     for(int i=1;i<=n;i++){
13         scanf("%d", &a[i]);
14         sum[i] = (sum[i-1] + a[i]) % 7;
15     }
16     for(int i=1;i<=n;i++)
17         last[sum[i]] = i;
18     for(int i=n;i>=1;i--)
19         first[sum[i]] = i;
20     for(int i=0;i<7;i++)
21         ans = max(ans, last[i]-first[i]);
22     printf("%d\n", ans);
23
24     return 0;
25 }

[USACO16JAN]子共七Subsequences Summing to Sevens

(0)
(0)

0条