문제링크

백준 #10986. 나머지 합

풀이

방법

1. PrefixSum을 구하고 각각에 모듈러 연산
2. 같은 모듈러 연산 결과들을 count
   "부분 합이 M으로 나누어 떨어지는 (i, j)쌍의 개수"
   -> (pSum[j + 1] - pSum[i]) % M = 0
   -> pSum[j + 1] % M = pSum[i] % M
   따라서, 같은 결과값을 갖는 것들을 count
3. numOf같은모듈러연산결과C2 조합수 계산 및 저장
   -> nCr에서 r == 2인 경우, 다음 수식으로 간단히 계산할 수 있음
   -> n * (n - 1) / 2

타입

각 입력들은 다음 범위를 가짐

• 1 <= N <= 10^6

• 1 <= M <= 10^3

• 0 <= A[i] <= 10^9
  이 범위들을 바탕으로 다음과 같이 각 변수들의 타입을 결정

• pSum: 부분합 배열(최대 10^9 * 10^9) => long
  (코드 내에서는 주기성을 띄는 모듈러 연산의 특징 때문에 모두 배열에 저장할 필요가 없다고 생각해서 int형 하나만 사용함)

• remainders count: 같은 나머지 결과 카운트 배열(최대 10^6) => int

• result: 구간의 합이 M으로 나누어 떨어지는 구간의 개수(최대 10^6 * 10^6 / 2) => long

코드

import java.util.Scanner;

public class SumOfRemainders {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        long[] array = new long[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }

        //long[] pSum = new long[n + 1];
        int pSum = 0;
        int[] remainders = new int[m];
        remainders[0]++;
        for (int i = 0; i < n; i++) {
            pSum += array[i];
            pSum %= m;
            remainders[pSum]++;
        }

        long result = 0;
        for (int i = 0; i < m; i++) {
            if (remainders[i] > 1) {
                result += (long)remainders[i] * (long)(remainders[i] - 1) / 2;
            }
        }

        System.out.print(result);
    }
}

🔥🔥🔥