[C/C++] 백준 10986번 - 나머지 합

백준 10986번 C++

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

10986번: 나머지 합

    ● (A+b) % C는 ((A%C) + (B%C))와 같다. 다시 말해 특정 구간 수들의

        나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일함

    ● S[j] %M의 값과 S[i] %M의 값이 같다면 (S[j]-S[i]) % M은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로

        업데이트하고 S[i]와 S[j]가 같은 (i,j,)쌍을 찾으면 원본 배열에서 i+1부터 j까지의 구간 합이 M으로 나누어 떨어짐 

    1. 배열 A의 합 배열 S를 생성하기

    2. 합 배열 S의 모든 값을 M으로 나머지 연산을 수행해 값을 업데이트 하기

    3. 변경된 합 배열에서 원소 값이 0인 개수만 세어 정답에 더하기

    4. 변경된 합 배열에서 원소 값이 같은 인덱스의 개수를 세고 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더하기

 

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

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

	int N, M;
	cin >> N >> M;

	vector<long> S(N, 0); //배열 생성
	vector<long> C(M, 0);

	long count = 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 remainder = S[i] % M; 
		if (remainder == 0) // 나머지 연산을 했을 때 나누어 떨어지므로 정답에 더하기
			count++;
		C[remainder]++;

	}

	for (int i = 0; i < M; i++) {
		if (C[i] > 1) // 나머지 연산 후 0이 아닌 원소들에 한하여 2개의 원소를 뽑는 모든 경우의 수를 구하기
			count = count + (C[i] * (C[i] - 1) / 2);
	}

	cout << count;
}