알고리즘
구간합 정의 : i ~ j 까지의 구간합 = (1~ j 까지의 구간합) - (1 ~ i -1 까지의 구간합)
위 정의에 따라 우리가 구해야하는 (i ~ j 까지의 구간합) % m = 0 은
((1~ j 까지의 구간합) % m - (1 ~ i -1 까지의 구간합) % m) % m 과 같음
따라서 (1~ j 까지의 구간합) % m = (1 ~ i -1 까지의 구간합) % m 인 (i, j) 가 조건을 만족함.
코드
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
#include <iostream>
typedef long long ll;
using namespace std;
int n, m, num[1000100], save[1100];
ll sum[1000100];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
cin >> num[0];
sum[0] = num[0];
for (int i = 1; i < n; i++) {
cin >> num[i];
sum[i] = sum[i - 1] + num[i];
}
save[0] = 1;
for (int i = 0; i < n; i++)
save[sum[i] % m]++;
ll cnt = 0;
for (int i = 0; i < m; i++) {
ll x = save[i] -1;
cnt += (x * (x + 1) / 2);
}
cout << cnt;
}