반응형
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
long long ans = 0;
int tmp = 0;
vector<long long> map(m, 0);
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
tmp = (tmp + a)%m;
map[tmp]++;
if (tmp == 0) {
ans++;
}
}
for (int i = 0; i < m; i++) {
ans += map[i] * (map[i] - 1) / 2;
}
cout << ans << '\n';
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 7662번 : 이중 우선순위 큐 - priority queue & map (0) | 2022.03.10 |
|---|---|
| 백준 16139번 : 인간 - 컴퓨터 상호작용 - 구간 합 C++ (0) | 2022.03.10 |
| 백준 16236번 : 아기상어 - BFS C++ (0) | 2022.03.09 |
| 백준 11660번 : 구간 합 구하기 5 - 누적합 C++ (0) | 2022.03.09 |
| 백준 1493번 : 박스 채우기 - 그리디 , 분할정복 C++ (0) | 2022.03.08 |