boj 10986: 나머지 합

누적합은 앞에서부터 누적해서 더한 값을 뜻한다.

s[i] = a[i]+a[2]+...+a[i]

 

이 문제는 (a[i]+...+a[j])%m인 (i, j) 쌍의 갯수를 구하는 문제이다.

누적합을 구해두고 for문으로 (a[i]+...+a[j])를 구하면 O(N^2)만에 풀 수 있지만,

n<=10^6이고 시간 제한이 1초이므로 다른 방법을 생각해야 한다.

 

 (a[i]+...+a[j])%m == 0

<=> (s[j]-s[i-1])%m == 0

<=> s[j]%m == s[i-1]%m 와 같으므로

 

mod[k]: s[i]%m == k인 i의 갯수를 저장한다면

mode[k]C2를 모두 더하면 된다.

 

주의할 점은 s[i]%m==0인 i는 그 자체로 답이 되므로 바로 ans++해준다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int m=in.nextInt();
		
		int sum=0;
		long mod[]=new long[m];
		long ans=0;
		
		for(int i=0;i<n;i++) {
			int input=in.nextInt();
			sum+=input;
			sum%=m;
			mod[sum]++;
			
			if(sum==0) {
				ans++;
			}
		}
		
		for(int i=0;i<m;i++) {
			long value = mod[i];
			long combination = value*(value-1)/Long.valueOf(2);
			ans+=combination;
		}
		System.out.println(ans);
	}
}