[백준 10986] 나머지 합

문제 링크 => 10986번: 나머지 합 (acmicpc.net)

10986번: 나머지 합

 

 

누적합을 이용한 문제이다.

 

i 번째에서 j 번째까지 원소들의 합이 M으로 나누어 떨어지는 모든 경우를 구해야 한다.

 

이해하기 쉽도록 예시를 들어보도록 하자.

 

 

ex ) 원소 5개 [1, 2, 3, 4, 5] 이 있고 3 으로 나누어 떨어지는 모든 경우의 수를 구하시오.

 

 

1. 배열 A에 대한 정보는 다음과 같다.

 

1

2

3

4

5

 

2. sum[i] = (A[1] + A[2] + ... A[i] ) % M 이라고 할 때 배열 sum 을 구해보도록 한다. 

 

1

0

0

1

0

 

3. 원소 i 번째에서 j 번째의 합을 S(i ~ j) 라고 하자. (sum[0] = 0)

    S(i ~ j) = sum[j] - sum[i - 1]   

    이때 sum[j] < sum[i - 1] 일 경우 음수이므로 Modular 연산을 고려해보자.

    S(i ~ j) = (sum[j] - sum[i - 1]) % M 

               = (sum[j] - sum[i - 1] + M) % M  <= M을 더하여 무조건 양수가 나오도록 해준다.

 

    S(i ~ j) 가 0 일 경우 원소 i 번째에서 j 번째의 합이 M 으로 나누어 떨어진다는 것은 확실하다.

    즉, 이러한 경우를 모두 counting 하도록 해야 한다.

 

주의해야 할 점 

 

(1) sum[x] = 0 인 경우는 그 자체로도 M 으로 나누어 떨어지기 때문에 이 경우는

     따로 counting 해야 한다.

(2) Worst case 인 경우 (모든 원소가 동일하며 전부 M 으로 나누어 떨어지는 경우) int 형 범위를 벗어나므로

      long long 형으로 설정해줘야 한다.

 

 

Solution Code

      

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, M;
long long A[1 << 20], cnt[1 << 10];

void solve() 
{
	int i;
	long long result;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++) {
		scanf("%lld", &A[i]);
		A[i] = (A[i] + A[i - 1]) % M;
		cnt[A[i]]++;
	}

	result = 0;
	for (i = 0; i < M; i++) {
		if (i == 0) result = (cnt[i] * (cnt[i] + 1)) / 2;
		else result += (cnt[i] * (cnt[i] - 1)) / 2;
	}

	printf("%lld", result);
}

int main(void)
{
	solve();

	return 0;
}