[10986 - JAVA] 나머지 합

 

문제

 

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

 

제출

 

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

public class Main {

    public static int n, m;
    public static long result;
    public static long[] num_list;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        num_list = new long[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            num_list[i] = num_list[i - 1] + Long.parseLong(st.nextToken());
        }

        HashMap<Integer, Integer> hashMap = new HashMap<>(m);

        for (int i = 0; i < m; i++) {
            hashMap.put(i, 0);
        }

        for (int i = 1; i <= n; i++) {
            Integer value = (int) (num_list[i] % m);
            hashMap.put(value, hashMap.get(value) + 1);
        }

        result = hashMap.get(0);
        for (int value : hashMap.values()) {
            result += (long) value * (value - 1) / 2;
        }

        System.out.println(result);

    }
}

 

누적합을 이용해 값을 합치고 m으로 나눈 값의 나머지들 각각의 개수 별로 k * (k-1) / 2를 구하면 m 값에 해당하는 개수를 알 수 있다.