백준 10986 c++ "나머지 합" -PlusUltraCode-

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

 

[필자 사고]

이 문제를 풀기 위해서는 2가지 방법을 알고 있어야 된다.

 

1. S[i] = S[i-1] + arr[i]   << 구간합을 구하는 공식이다. 

 

 

2. a%M + b%M  == (a+b)%M  이라는 공식을 알고 있어야 된다. 

 

3. S[i]%M 으로 나눴을 때 같은 숫자가 나오는 경우가 있다.

S[2]%M = 1

S[4]%M = 1 인 경우

 

S[4] - S[2] 를 하게 되면 나머지가 0 으로 바뀌게 된다.

 

이말은 즉 구간합 2를 제외한 3하고4는 나머지가0 의 합이라는 소리다.

 

즉 같은 숫자가 나온것들끼리 컴비네이션으로 nC2 를 하게 되어 더해주면 된다.

 

또한 마지막으로 주의할점은 문제에서 주어지는 숫자들의 크기이다.

 

상당한 큰 숫자들이 있따. 문제를 잘 읽고  int 혹은 long 을 쓸지 잘 판단해야 된다.

 

[소스코드]

#include <iostream>
#include <vector>


using namespace std;

int N, M;
long resultCount = 0;

vector<long> arr;
vector<long> S;
vector<long> namuji;

void Input() {
	cin >> N >> M;

	arr.resize(N + 1,0);
	S = arr;
	namuji.resize(M + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void makeSum() {
	for (int i = 1; i <= N; i++) {
		S[i] = (S[i - 1] + arr[i]);
		
	}
	for (int i = 1; i <= N; i++) {
		S[i] = S[i] % M;
		if (S[i] == 0)resultCount++;
		namuji[S[i]]++;
	}
}

long combination(long num) {
	return num*(num - 1) / 2;
}

void GameStart() {
	Input();
	makeSum();
	
	for (int i = 0; i < namuji.size(); i++) {
		int count = namuji[i];
		if (count ==0)continue;

			resultCount += combination(count);
		
	}
}

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

	GameStart();

	cout << resultCount;
}