[골드 3] 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으로 나누어 떨어지는 구간의 개수를 출력한다.

 

예제 입력 1

5 3
1 2 3 1 2

 

예제 출력 1

7

 

---

import java.io.*;
import java.util.*;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 수열의 개수
        int M = Integer.parseInt(st.nextToken()); // 나눌 값

        long[] S = new long[N]; // 합 배열
        long[] C = new long[M]; // 나머지가 같은 인덱스 카운트하는 배열
        long answer = 0;
        
        st = new StringTokenizer(br.readLine());
        
        // 합 배열 구하기
        S[0] = Integer.parseInt(st.nextToken());
        for(int i=1; i<N; i++) {
            S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
        }

        // 나머지 값 구하고 0인 경우 카운트 1 증가
        for(int i=0; i<N; i++) {
            int r = (int) (S[i] % M);

            if(r == 0) answer++;
            C[r]++;
        }

        for(int i=0; i<M; i++) {
            // 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수 더하기
            if(C[i] > 1) {
                answer += (C[i] * (C[i] - 1) / 2);
            }
        }

        System.out.println(answer);
        
        br.close();
    }
}