CSES 2. Subarray Divisibility (1662)

출처: https://cses.fi/problemset/task/1662 

---

문제 설명

Given an array of n integers, your task is to count the number of subarrays where the sum of values is divisible by n.

입력 

The first input line has an integer n: the size of the array.

The next line has n integers a_1,a_2,…,a_n: the contents of the array.

출력 

Print one integer: the required number of subarrays.

입력 예

5
3 1 2 7 4

출력 예

1

제약조건

• 1 <= n <= 2x10^5
• - 10^9 <=  a_i <= 10^9

---

문제 풀이 내용

배열의 입력값을 modulo 연산을 해서 더한 값을 저장한다. 이 값들은 입력하기 전에 한번더 modulo 연산을 하도록 하고, 음수인 경우는 양수가 되도록 한다. 이렇게 만들어진 값들을 map에 입력해서, 이 합의 배열의 차가 0이 되는 경우의 수를 센다. 

프로그램 내용

...
    vector <long> num_arr(nNum, 0);
    vector <long> sum_arr(nNum+1, 0);

    for(int idx=0; idx < nNum; ++idx)
        cin >> num_arr[idx];
        sum_arr[idx+1] = (sum_arr[idx] + num_arr[idx])% nNum;
        if ( sum_arr[idx+1] < 0)
            sum_arr[idx+1] = (sum_arr[idx+1]+nNum) % nNum;
        else
            sum_arr[idx+1] %= nNum;

    long long ar_count = 0;
    map <int, int> r_map;
    r_map[0] = 1;

    for(int idx=0; idx < nNum; ++idx)
        auto au_it = r_map.find(sum_arr[idx+1]);
        if (au_it != r_map.end())
            ar_count += au_it->second;
        r_map[sum_arr[idx+1]]++;
...

 

Sorting and Searching ( link )