C++ / 10986 / 나머지 합 ( 누적 합 )

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

문제 요약

수 N개 A1, A2, ..., AN이 주어집니다.

이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성해야합니다.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 합니다.

문제 풀이

1. 나머지별로 개수를 카운트 하기 위해서 cnt 배열을 넉넉하게 만듭니다.

2. 수를 입력 받음과 동시에 누적합을 만들어 갑니다.

3. 누적합을 m으로 나눴을때 나머지 개수를 세어줍니다.

4.  cnt[i]는 누적합을 m으로 나눴을 때 나머지가 i인 경우가 몇 번 발생했는지 카운트한 값입니다. 이때, 같은 나머지를 가진 두 누적합을 고르면 그 두 누적합의 차이는 m의 배수가 됩니다.

cnt[i]가 2개 이상이라면, cnt[i] * (cnt[i] - 1) / 2는 그들 중 2개를 고르는 경우의 수, 즉 조합을 계산한 것입니다. 이 값만큼 ans에 더해줍니다.

같은 나머지를 가진 두 누적합을 선택했을 때 그 차이는 항상 m의 배수가 된다는 특성을 이용하여, 그럴 경우의 수를 모두 더해주기 위해 nC2 (조합)를 사용합니다.

5. 마무리로 누적합이 m의 배수인 경우도 추가합니다.

주의할 점

모듈러 연산과 누적합을 알고 풀어야합니다...

어렵더라구요..

코드

#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;

typedef long long int ll;

ll n, m;
ll cnt[1000004];
ll sum = 0;
ll ans = 0;
int main()
{
	cin >> n >> m;

	for (ll i = 0; i < n; i++)
	{
		ll a;
		cin >> a;
		// 누적 합
		sum += a;
		// 누적합 중에 m으로 나누었을 때 나머지가 같은 것 카운트
		cnt[sum % m]++;

	}
	// cnt[0]: 누적합 자체가 M의 배수인 경우 (s[j] % m == 0)
	// cnt[i]에서 같은 나머지를 가진 두 개의 누적합을 선택하는 경우
	for (int i = 0; i < n; i++)
	{
		// 같은 나머지를 가진 두 개의 누적합을 골라서 선택하면 항상 m의 배수가 됨
		// s[i] % m = s[j] %m 이면 
		// s[i] % m - s[j] % m = 0 이라는 것은 s[j] - s[i] 는 무조건 m의 배수임
		// 그래서 r은 2개를 골랐을 경우의수를 구해야 하기 때문에 2임
		// nCr 공식 ( 경우의수 구하는 것 )
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	// 마지막으로 누적합 자체가 m의 배수인 경우 ( 나머지가 0 )경우를 더해줌
	cout << cnt[0]+ans;
	return 0;
}

예제

5 3
1 2 3 1 2

결과