백준 10986번 나머지 합

https://www.acmicpc.net/problem/10986

 

아이디어:

1. 1차원 long vector 생성.

2. 합 vector S 생성, S 각 요소에 대해 M으로 나눈 나머지로 변경

ex) 백준 예제 입력: 1 2 3 1 2 > 1 3 6 7 9 > 1 0 0 1 0

3. 먼저 나온 0은 하나씩 더해주기 = 3

4. 같은 나머지가 나온 요소에 대해서 조합 x C 2를 적용

ex) 나머지 0인 요소가 3개이므로 3 C 2, 나머지 1인 요소가 2개이므로 2 C 2

조합 = x * (x - 1) / 2

같은 나머지가 나온 요소 쌍이 M으로 나누어 떨어지는 구간인 이유:

구간 합 (i, j) = S[j] - S[i - 1]

(S[j] − S[i−1]) % M = 0

(S[j] % M) − (S[i−1] % M) = 0

S[j] % M= S[i−1] % M

 

// 10986

#include <iostream>
#include <vector>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long N, M, temp, answer = 0;
	
	cin >> N >> M;

	vector<long> S(N + 1, 0);
	vector<long> C(M, 0);

	for (long i = 1; i <= N; i++) {
		cin >> temp;
		S[i] = S[i - 1] + temp;
	}

	for (long i = 1; i <= N; i++) {
		S[i] %= M;
		C[S[i]]++;
	}

	answer += C[0];

	for (long i = 0; i < M; i++) {
		if (C[i] > 1) {
			answer += (C[i] * (C[i] - 1)) / 2;
		}
	}

	cout << answer;

	return 0;

}