[백준] 10986번 나머지 합

10986 나머지 합

문제

---

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

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

입력

---

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

---

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

---

풀이)

update 쿼리가 없고, 구간 합만 구해서 나머지를 확인하면 되는 문제라

segment tree 가 아니고 prefix sum 을 이용한 문제다.

그리고 모든 구간을 직접 prefix sum을 이용해 나머지를 확인하면 시간 초과가 나는 문제여서

모듈러 성질을 생각해서 다른 방법을 사용해야 한다.

prefix sum 성질

a[1] + a[2] + ... + a[i] = sum[i];

a[L] + a[L + 1] + a[L +2]+ ... + a[R] = sum[R] - sum[L-1];

모듈러 성질

(A + B) % C = (A % C + B % C) % C

따라서,

[L,R] 구간합의 나머지가 0인지는 (sum[R] - sum[L-1]) % M = 0

(sum[R] % M - sum[L-1] % M) % M = 0

누적합에서 나머지가 같은 것끼리 조합하면, 그것이 M으로 나누어 떨어지는 구간의 개수

sum[0] ~ sum[N]을 M으로 나눈 나머지가 각각 몇개씩 있는지 계산한 뒤, 그것을 이용한다.

문제 예시) 

N=5, M=3

{1 2 3 1 2} 의 경우, sum[] = { 1 3 6 7 9 } 나머지는 {1 0 0 1 0}

3으로 나눈 나머지가 0인 것은 3개, 1인 것은 2개, 2인 것은 0개

3 + 3 combination 2 + 2 combination 2가 정답 

(나머지가 0인 구간은 2개 조합안하고도 M으로 나누어 떨어지므로 개수에 더해줘야 한다.)

↓

구간 (구간이 1부터 시작해서 5까지 있다고 할 때)

나머지 0 => 3개                       (1,2) / (1,3) / (1,5)

나머지 0 조합 =>3*2/2 = 3개     (1,3-1,2) = (3,3) / (1,5-1,2) = (3,5) / (1,5 - 1,3) = (4,5)

나머지 1 조합 =>2*1/2 = 1개     (1,4-1,1) = (2,4)

코드)

#include <stdio.h>
using namespace std;
 
int N, M; // N <= 1000000
long long arr[1000001];
long long cnt[1001];
 
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        int temp;
        scanf("%d", &temp);
        arr[i] = (arr[i - 1] + temp) % M;
        cnt[arr[i]]++;
    }
    long long result = cnt[0]; //구간 자체가 m으로 나눠지는 
    for (int i = 0; i < M; i++) {
        result += (cnt[i] * (cnt[i] - 1)) / 2;//나머지가 같은 횟수끼리 2개 조합
    }
    printf("%lld", result);
 
    return 0;
}