백준10986 나머지 합

작성일 | In

문제 링크

  • http://icpc.me/10986

사용 알고리즘

  • Prefix Sum

시간복잡도

  • O(N)

풀이

Update 쿼리가 없고, 연속된 구간의 합에 관련된 쿼리문제이므로 prefix sum을 먼저 생각해볼 수 있습니다.

구간의 합을 M으로 나눈 나머지가 0인 구간의 개수를 세야 합니다.
시작점과 끝점을 잡고 돌리면 O(N2)이기 때문에 TLE가 뜹니다. 최적화시킬 아이디어를 찾아야 합니다.

입력 예제로 주어진

1
2
5 3
1 2 3 1 2

의 누적합을 구하면 1 3 6 7 9 입니다. 3으로 모듈러 연산을 하면 1 0 0 1 0 이 나옵니다.

모듈러 연산의 성질을 다시 한 번 생각해봅시다.
(A + B) % C와 (A%C + B%C) % C의 결과는 동일합니다. 덧셈 뿐만 아니라 뺄셈, 곱셈에 대해서도 성립합니다.

다시 문제로 돌아와서, [i, j] 구간의 합은 sum[j] - sum[i-1] 이고, 문제에서는 (sum[j] - sum[i-1]) % M 이 0인 순서쌍 (i, j)의 개수를 묻고 있습니다.
(sum[j] - sum[i-1]) % M = 0 이라면 (sum[j]%M) - (sum[i]%M) = 0 입니다.
이 점을 활용해서 sum[i]%M = sum[j]%M 인 쌍의 개수를 구해주면 됩니다.
그러나 sum[x]%M = 0 인 경우에는 자기 혼자만으로도 나누어 떨어지는 구간이 되기 때문에 sum[x]%M == 0 인 경우는 따로 카운팅해야 합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cnt[1010];
ll arr[1010101];

int main(){
	int n, m; cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		arr[i] += arr[i-1];
		arr[i] %= m;
		cnt[arr[i]]++;
	}

	ll ans = cnt[0];
	for(int i=0; i<m; i++){
		ll now = cnt[i];
		ans += now * (now - 1) / 2;
	}
	cout << ans;
}