[BOJ/C++] 10986 나머지 합

구간 합을 이용해야 하는 문제입니다.

$Ai + ... + Aj (i<j)$ 까지의 합이 M으로 나누어 떨어지는 $(i,j)$의 쌍을 구해야합니다

구간 합 $S[j] - S[i]$는 $i+1$ 부터 $j$까지의 구간 합 이므로

$S[j]$%M의 값과 $S[i]$%M의 값이 같다면 $(S[j]-S[i])$%M의 값은 0이다

즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 $S[j]$와 $S[i]$가 같은 $(i, j)$ 쌍을 찾으면 됩니다.

답 구하기

1. 나머지가 0인 합 배열의 원소 갯수 더해주기

• 나머지가 0인 합 배열의 원소는 0부터 i까지의 구간 합이 M으로 나누어 떨어진 상태입니다.

2. 나머지 값이 같은 합 배열의 개수를 구한다

• 원소 값이 같은 합 배열은 $S[j]-S[i]=0$ 이므로 나머지 값이 같은 인덱스 2개를 뽑는 조합을 찾으면 됩니다.
• 값이 같은 원소가 3개 있다면 $3C2$ -> 3개
• M으로 나눈 나머지의 수는 M개 입니다.

// boj g3 10986
// 나머지 합

// (A+B)%C는 ((A%C)+(B%C))%C와 같다
// N개중 2개를 선택하는 방법의 수는 N*(N-1)/2 이다
#include <iostream>
#include<vector>

using namespace std;

static int N, M;
static vector<long> s;
static vector<long> m;
static long result = 0;


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;

	s.resize(N+1, 0);
	m.resize(M, 0);

	for(int i=1; i<=N; i++)
	{
		int tmp;
		cin >> tmp;
		s[i] = s[i - 1] + tmp;
	}

	for(int i=1; i<=N; i++)
	{
		int remain = s[i] % M;
		// 나머지가 0인 합 배열의 원소 더해주기
		if (remain == 0)
			result++;

		// 나머지가 같은 원소의 개수 더해주기
		m[remain]++;
	}

	for(int i=0; i<M; i++)
	{
		// 나머지가 같은 원소가 2개 이상 있다면
		// nC2  구하기
		if(m[i]>1)
		{
			result += (m[i] * (m[i]-1) / 2);
		}
	}

	cout << result;

	return 0;
}