10986 나머지 합

 

예제를 가지고 설명해보면

 

5 3
1 2 3 1 2

 

누적합을 통해서 문제를 풀 수 있다.

특히 누적합%M 값을 이용한다.

 

i	0	1	2	3	4
입력값	1	2	3	1	2
누적합	1	3	6	7	9
누적합%M = A[i]	1	0	0	1	0

 

 

우리는 A[i] 값을 이용하는데,

 

정답으로 출력할 건수를 생각해보면,

 

1) A[i] = 0 인 부분

i = 1,2,4 인 경우이다.

각각 누적합이 3,6,9인 경우로 M(=3) 으로 나누면 나머지가 0 이므로 정답이 된다.

 

1-1)

누적합이 3인 경우 :  i = 0 부터 i = 1 까지의 합,

누적합이 6인 경우 : i = 0 부터 i = 2 까지의 합

누적합이 9 인 경우 : i = 0 부터 i = 4 까지의 합

 

즉, 3가지 경우가 있다. 

 

 

1-2) 

다른 경우도 생각해 볼 수 있다.

i = 1,4의 경우를 생각하면,

A[4] - A[1] = 0 이다. 

이 경우도 M으로 나눈 값이 0 이 되는 것이므로 정답이 된다.

 

즉, 

A[4] => i = 0 부터 i = 4까지의 누적합

A[1] => i = 0 부터 i = 1까지의 누적합

A[2] - A[1] => i = 2 부터 i = 4까지의 누적합.

 

이때 i = 2~4까지의 누적합은 6 이며,

 M(=3) 으로 나눴을 때 나머지가 0 인 경우이다.

 

그 외에도

i = 1,2 

i = 2,4 의 경우도 마찬가지이다. 

 

이처럼,  A[i] = 0 인 경우들을 순서를 생각하지 않고 2가지 뽑는 경우를 생각하면 된다.

 

 

이때,  sum 배열을 활용하는데,

sum[0] => A[i] = 0 인 것들의 총 개수 

sum[1] => A[i] = 1 인 것들의 총 개수 

sum[2] => A[i] = 2 인 것들의 총 개수라고 하면,

 

 

i	0	1	2
sum[i]	3	2	0

 

sum[0]  을 만족하는 것 중에,

순서를 생각하지 않고 2개씩 뽑는 경우를 생각하면 된다.

sum[0] = 3가지 이므로,

조합으로, 3*2/2 = 3 가지의 경우를 찾을 수 있다. 

 

i = 1,2 인 경우,

i = 1,4 인 경우,

i = 2,4 인 경우이다. 

 

 

 

 

2) A[i]= 1 인 부분

i = 0, 3 인 경우이다.

이 경우도,  sum[1] 인 경우에서 순서를 생각하지 않고 2가지 뽑으면 된다.

2*1/2 = 1 이 되어,

1가지 경우를 찾게 된다. 

 

2) A[i]= 2 인 부분

이 경우는 없으므로 

0가지 이다. 

 

따라서 총, 

3 + 3 + 1 + 0 = 7가지가 정답이 된다. 

 

 

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

public class Main {
	
    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());
       	  int sum[] = new int[M];      	
   
       	  st = new StringTokenizer(br.readLine(), " ");
       	  int a = 0;
       	  
       	  for(int i=0; i<N; i++) {
       		  int b = Integer.parseInt(st.nextToken());
       		  a= (b + a)%M;       		  
       		  sum[a] ++;
       	  }      	 
			
       	  long count =  sum[0];
       	       	  
       	  for(int i=0; i<sum.length; i++) {       		 
       		  
       		  count+=(long) sum[i] * (sum[i]-1)/2;	      		  
       	  }
       	
     System.out.println(count);
   }
}