Light oj 1134

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1134

题意：

给你n个数，问你多少个连续的数的和是m的倍数。

思路：

前缀和取模一下就好了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 const int N = 1e5 + 5;
 6 int a[N];
 7 int sum[N], cnt[N];
 8 
 9 int main()
10 {
11     int t, n, m;
12     scanf("%d", &t);
13     for(int ca = 1; ca <= t; ++ca) {
14         scanf("%d %d", &n, &m);
15         memset(cnt, 0, sizeof(cnt));
16         cnt[0]++;
17         for(int i = 1; i <= n; ++i) {
18             scanf("%d", a + i);
19             sum[i] = (sum[i - 1] + a[i]) % m;
20             cnt[sum[i]]++;
21         }
22         long long ans = 0;
23         for(int i = 0; i < m; ++i) {
24             ans += (long long)cnt[i] * (cnt[i] - 1) / 2;
25         }
26         printf("Case %d: %lld
", ca, ans);
27     }
28     return 0;
29 }