백준 10896 나머지합

www.acmicpc.net/problem/10986

10986번: 나머지 합

이 문제는 M으로 나누어 떨어지는 구간을 구하는 문제이다. 카테고리를 보면 누적합이라고 되어있는데 누적합이라는 방법을 사용해서 간단하게 해결할 수 있다. 

 

여기서 누적합이란 무엇일까? 

 

누적합은 계속해서 덧셈을 해주어서 누적되어있는 구간을 만들고 그 누적합끼리 뺌으로써 원하는 구간의 합을 구할 수 있는 것을 의미한다.

 

위 그림을 보면 훨씬 쉽게 이해할 수 있다. 

 

위 ~ 표시는 인덱스 0에서 1까지 더한 값, 0 ~ 2는 0에서 2까지 더한 값을 의미한다. 

위의 예시 처럼 

 

0 ~ 4의 합에서 

0 ~ 3까지의 합을 빼주면 4의 정보를 얻을 수 있다. 

0 ~ 2까지의 합을 뺴주면 3, 4의 합 값을 얻을 수 있다. 

0 ~ 1까지의 합을 빼주면 2, 3, 4의 합 값을 얻을 수 있다. 

0을 빼주면 1, 2, 3, 4의 합 값을 얻을 수 있다. 

 

누적합의 이러한 성질을 활용하면 이 문제는 쉽게 풀 수 있다. 

 

M으로 나누어 주었을 때 나머지가 0이 되는 값을 찾는 것이니 각각의 누적합에 나누기를 하여 개수를 구해준다. 

같은 나머지 값이 여러개인 경우 ((나머지 조합 수) * (나머지 조합 수 - 1))/2 와 같은 공식으로 개수를 구해줄 수 있다. 

 

왜 이런것이 가능한걸까? 

 

만약 3으로 나누었을 때 같은 나머지를 나타내는 2, 11과 같은 경우는 두 값을 빼주었을 때 9가 되어 나머지가 0이 되는 부분이 생긴다. 그럼 공통된 나머지를 갖는 수에서 2개를 뽑을 수 있는 수를 차례대로 구해주면 된다. 

 

하지만 또 다른 예외 상황이 있다. 

 

만약 나머지가 0인 경우에는 어떻게 될까? 0인 경우에도 당연히 위의 수식으로도 구해줄 수 있지만 자기 자체의 범위로도 문제의 조건을 만족한다. 따라서 최종 결과값에 나머지가 0이되는 수의 개수를 더해주면 정답이 된다. 

 

#include <cstdio>
#include <vector>
#define ll long long

using namespace std;

int main(){
	ll M, N, inputNum;

	vector<ll> num(1000002), result(1002);
	scanf("%lld %lld", &N, &M);

	for(int i = 1; i <= N; i++){
		scanf("%lld", &inputNum);
		num[i] += inputNum + num[i-1];
	}

	for(int i = 1; i <= N; i++){
		result[num[i] % M]+=1;
	}

	ll ret = result[0];

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

	printf("%lld", ret);

}