[Gold / 10986] 나머지 합

문제 링크

---

🔷 분류

수학, 누적 합

✒️ 문제 설명

수 N개 A₁, A₂, …, A_N이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, A_i + … + A_j (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

⬅️ 입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10⁶, 2 ≤ M ≤ 10³)

둘째 줄에 N개의 수 A₁, A₂, …, A_N이 주어진다. (0 ≤ A_i ≤ 10⁹)

➡️ 출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	long tot = 0;
	cin >> n >> m;
	vector<long> S(n, 0);
	vector<long> C(m, 0);
	cin >> S[0];
	for(int i = 1; i < n; i++) {
		int temp;
		cin >> temp;
		S[i] = S[i-1] + temp;
	}
	for(int i = 0; i < n; i++) {
		int na = S[i] % m;
		if(na == 0) tot++;
		C[na]++;
	}
	for(int i = 0; i < m; i++) {
		if (C[i] > 1) {
			tot += (C[i] * (C[i]-1) / 2);
		}
	}
	cout << tot;
	return 0; 
}