백준 10986 번 : 나머지 합

문제 링크 : https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

 

 문제 설명 

 

1. N개의 숫자와 M 이주어진다

2. 연속된 부분구간의 합이 M으로 나누어 떨어지는 구간의 갯수를 출력하면됨 .

 

 

 

 알고리즘 

 

1. 일단 어렵다 . 알고리즘을 직접생각해내는게 엄청 어렵다 그래서 참고했다 ^ ^

2. (a + b) % MOD = (a % MOD + b % MOD) % MOD 를 이용해야된다 .

3. 예제를 살펴보면 (1+2+3+1)%3 (구간 (1,4) 의 합 의 나머지..)  == 1%3  (구간 (1,1) 의나머지 )= 1  

   - > (2,4) 구간합의 나머지 -> (2+3+1)%3 =0 

   - > 즉 , 구간 합의 나머지가 같은 것 들의 갯수를 구해서 그 구간들 중 2개를 뽑으면 그걸로 나머지가 0인 구간을 찾    - > 을 수있다. 

4. 구간합배열의 나머지를 배열에 저장 

5. 나머지 배열의 크기가 3이라고 하면  그중 2개의 구간만 고르면된다 그러면. 3C2 가되어

   -> 나머지 가 0인 경우의 수 3  

6 .0~M-1 까지 구한뒤  다더해준다 그리고 구간합의 나머지가 0인경우는 자기자신만 있어도 0이되므로 각각 1씩더 해    준다.

 

 

 

 코드 

 

#include<iostream>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M;
    long long sum = 0;
    long long mod[1001] = { 0, };
    long long result = 0;
    cin >> N >> M;
 
    
 
    for (int i = 0; i < N; i++) {
        
        int a;
        cin >> a;
        sum = (sum + a) % M;
        if (!sum)result++;
        mod[sum]++;
    }
 
    for (int i = 0; i <M; i++) {
        result = result+mod[i] * (mod[i] - 1) / 2;
    }
    cout << result;
 
}