[백준] 10986번 나머지 합

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        long[] sum = new long[m]; // 나머지 별 개수를 저장할 배열
        long answer = 0;
        long prefixSum = 0;

        sum[0] = 1; // 초기값 설정

        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + kb.nextLong()) % m;
            answer += sum[(int) prefixSum]; // 이전까지의 누적합을 더함
            sum[(int) prefixSum]++; // 현재 누적합의 개수를 증가시킴
        }

        System.out.println(answer);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner kb = new Scanner(System.in);
    	int N = kb.nextInt();
    	int M = kb.nextInt();
    	
    	int sum = 0;
    	int[] count = new int[M];

    	for(int i=0; i<N; i++) {
    		sum = (sum+ kb.nextInt())%M;
    		count[sum]++;
    	}
    	
    	long answer = count[0];
    	
    	for(int i=0; i<M; i++) {
    		answer += (long) count[i] * (count[i]-1)/2;
    	}
    	System.out.println(answer);
    }
}

 

구간 합의 경우 sum[j] - sum[i] 로 구할 수 있는데 이 문제에서 M으로 나눈 나머지가 0인 쌍을 구해야한다.

(sum[j] - sum[i])%M = 0을 정리하면 sum[j]%M = sum[i]%M이다. 

따라서, sum[j]%M = sum[i]%M을 구하면 된다.

 

(1) sum[j]%M = sum[i]%M 

(2) sum[i] % M = 0 인 경우 (배열의 0부터 i까지의 구간의 합이 이미 M으로 나누어떨어진다)