[백준] 10986. 나머지합

https://www.acmicpc.net/problem/10986

문제 설명

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

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

($1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3$)

N개의 수 A1, A2, ..., AN ($0 ≤ Ai ≤ 10^9$)

풀이

누적합을 배열에 저장해놓고 nums[j]-nums[i-1] % M == 0으로 하였더니 시간 초과 (데이터 범위도 long으로 해야 한다)
nums[j] % M - nums[i-1] % M == 0 → nums[j] % M == nums[i-1] % M이면 구간합이 M으로 나누어 떨어진다.
따라서 누적합을 M으로 나눈 나머지를 배열에 저장하고, remain[나머지]++ 하여 나머지의 개수를 세어준다.
나머지 개수가 2개 이상인 것들만 무작위로 2개 뽑아 개수를 세어주고,
나머지가 0인 애들은 2개를 뽑지 않아도 이미 조건을 만족하므로 추가로 카운트해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_G3_10986_나머지합 {

	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[] nums = new long[N+1];
		long[] remain = new long[M];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			nums[i] = (nums[i-1] + Integer.parseInt(st.nextToken())) % M;
			remain[(int)nums[i]]++;
		}

		long count = remain[0];
		for (int i = 0; i < M; i++) {
			if(remain[i] >= 2) {
				long n = remain[i];
				count += n*(n-1)/2;
			}
		}
		
		System.out.println(count);
	}

}