[C++/백준] 10986번: 나머지 합

문제 링크

10986번: 나머지 합

 

풀이

누적합 문제인데, 모듈러 연산도 곁들인 ..
참고로 합 모듈러 연산은 (a+b)%m = ((a%m)+(b%m))%m이다.

1. 합이 M으로 나누어 떨어지는 구간을 구하면 되므로, 누적합의 모듈러를 구하는 것. 이 것은 위에 설명한 합 모듈러 연산으로 바꾸어 생각하면 된다.
   1. 값을 입력 받으면서 누적합의 모듈러를 구한다. 그렇게 나온 값의 총 개수를 구하기 위해 cnt 벡터에 넣어준다.
2. 각 결과값의 개수가 구해질 것이다.(cnt)
   1. 누적합의 모듈러 값이 0인 것은 해당하는 인덱스까지 누적합이 m으로 나누어 떨어진다는 것이고,
   2. 다른 두 개의 인덱스가 같은 모듈러 값을 가지면, 해당 인덱스부터 인덱스까지의 누적합이 m으로 나누어 떨어진다는 것이다.
3. 그래서 개수를 구한 것이고, answer에 cnt[0]값과, 개수가 2개 이상인 경우에는 2개를 뽑는 조합을 구해 더하면 된다.

표를 보면 더 쉽다

입력값	1	2	3	1	2
누적합	1	3	6	7	9
누적합 % m	1	0	0	1	0

 

코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    int modSum = 0;
    vector<long long> cnt(m);
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if (i == 0) modSum = tmp % m;
        else modSum = ((modSum % m) + (tmp % m)) % m;
        cnt[modSum]++;
    }

    long long answer = cnt[0];
    for (int i = 0; i < m; i++)
    {
        if (cnt[i] >= 2) answer += cnt[i] * (cnt[i] - 1) / 2;
    }

    cout << answer;
}