[10986] 나머지 합

---

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

10986번: 나머지 합

누적합 문제이다.

 

처음에 이중for문을 썼더니 시간 초과가 나서 2시간동안 풀었다.

 

질문 게시판에 설명되어있던 알고리즘을 참고하여 풀었다.

누적합을 M으로 나눈 나머지가 같은 것들끼리 빼면 나머지가 0이 되어 딱 나누어 떨어지게 된다. 

그 점을 이용하기 위해 L배열을 만들었다.

 

그리고 나머지가 같은 것들끼리의 구간합이 총 몇 개인지 알기 위해 R배열을 만들었다.

 

예제를 보면 이해가 더 쉬울 것 같다.

1) 입력 값이 1 2 3 1 2, M=3인 경우

2) 입력값이 4 2 8 7 1 5 9 2 4 3, M=4인 경우

 

 

전체 코드이다.

#include <iostream>
using namespace std;

int N, M;
long long S[1000001]; 
long long L[1001] = { 1, };
long long sum;
long long R[1000001];

void f() {
	// 0~i까지 누적합 계산
	// ex) R[3] = 1 + 2 + 3 = 6
	for (int i = 1; i <= N; i++) {
		if (i == 1)R[i] = 1;
		else R[i] = i + R[i - 1];
	}
}

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

	cin >> N >> M;

	f(); // 최대 N까지의 누적합을 계산하면 됨

	for (int i = 1; i <= N; i++)
	{
		long long temp; cin >> temp;
		S[i] = S[i - 1] + temp; // 입력값의 누적합
	}

	for (int i = 1; i <= N; i++) {
		// 입력값들을 M으로 나눈 나머지 개수 L배열에 저장
		// L[1] = 입력된 값을 M으로 나눈 나머지가 1인 입력값들의 개수
		L[S[i] % M]++;
	}

	for (int i = 0; i < M; i++) {
		if (L[i] - 1 >= 0) { // 쌍을 이뤄야 함
			sum += R[L[i]-1];
		}
	}

	printf("%lld", sum);
}