백준 10986번, 나머지 합 풀이

문제

백준 10986번

풀이

태그는 누적합 문제가 붙어있지만, 저는 수식 정리 연습 문제라고 느꼈습니다.

 

누적합을 아래와 같이 정의합니다.

$$ S(i, j) = \sum_{k=i}^j A[k] $$

(단, $i \leq j$)

한편, $ sum[i] = S(1, i) $의 배열을 만들어두면, 임의의 누적합 $ S(i, j) $에 대하여 $ sum[j] - sum[i - 1] $로 나타낼 수 있으므로 $O(1)$에 구할 수 있습니다. 

 

본격적인 수식 정리를 해보겠습니다.

---

$$ S(i, j) = sum[j] - sum[i - 1] = kM $$

(단, $k$는 자연수)

 

위 식에서 $M$으로 나눈 나머지를 구해봅시다.

* 우변인 $kM$이 항상 $M$의 배수이므로 $M$으로 나눈 나머지는 0이 됩니다.

$$ (sum[j] - sum[i - 1])\ \%\ M = 0 $$

 

$$ sum[j]\ \%\ M\ =\ sum[i - 1]\ \%\ M $$과 같이 정리할 수 있겠네요.

 

위 수식이 뜻하는 의미는 임의의 $i$와 $j$에 대해서 $ sum[j]\ \%\ M\ =\ sum[i - 1]\ \%\ M $를 만족하면, 문제에서 요구하는 "Ai+ ... + Aj(i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍" 중 하나가 됩니다.

---

그러면, 배열 $ B[i] = sum[k]\ \%\ M $가 $i$인 개수라고 하면, $ B[i] $에서 임의의 두 개의 값을 뽑아 $M$의 배수가 되는 $(i, j)$ 쌍의 개수를 구할 수 있습니다. ($ =\ _{B[i]}C_{2} $)

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	ll n, m, a, tmp = 0, ans = 0; cin >> n >> m;
	vector<ll> sum(m + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a;
		tmp += a; //tmp = 1 ~ i까지의 누적합
		sum[tmp %= m]++; //tmp % M의 값을 저장
		if (!tmp) ans++; //1 ~ i까지의 누적합이 0이면(M의 배수라면), (i, i)를 선택하여 한가지 경우의 수가 될 수 있음
	}

	for (const auto &c : sum) ans += c * (c - 1) / 2; //nC2
	cout << ans;
}