LightOJ-Solutions/1134-Be-Efficient.cpp at master · hackerkid/LightOJ-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;


long long fact_cal(int x)
{

	long long nplus1 = x;
	nplus1++;

	return (long long) (x * nplus1) / 2;

}

int main()
{

	int t;
	int n;
	int m;

	int a[500004];
	int count[500005];
	long long sum;

	scanf("%d", &t);


	for (int cs = 1; cs <= t; cs++) {
		scanf("%d", &n);
		scanf("%d", &m);

		memset(count, 0, sizeof(count));
		sum = 0;

		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}

		a[0] = a[0] % m;

		for (int i = 1; i < n; i++) {
			a[i] = (a[i-1] + a[i]) % m;
		}


		for (int i = 0; i < n; i++) {
			count[a[i]]++;
		}

		sum += count[0];

		long long temp;

		for (int i = 0; i <= 500000; i++) {
			sum = sum + fact_cal(count[i] -1);
		}

		printf("Case %d: %lld\n", cs, sum);

	}

}