백준 10986번 나머지 합

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

Algospot CHRISTMAS(https://jaimemin.tistory.com/487) 문제의 첫 번째 부분문제와 똑같은 문제였습니다.

알고리즘은 아래와 같습니다.

1. 부분합을 구할 때 M에 대해 모듈러 연산을 한 값을 저장하고 해당 값이 몇 번 나왔는지 기록합니다.

2. 해당 부분합의 모듈러 연산의 결과가 0이라면 M에 나누어떨어지므로 결과에 더해줍니다.

3. 같은 나머지가 나온 구간의 부분합은 M에 나누어떨어지므로 (해당 나머지가 나온 횟수)C2 를 구해주고 결과에 더해줍니다.

$$_{(해당 나머지가 나온 횟수)}C_2$$

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 1000000 + 1;

 

long long pSum[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        vector<long long> cnt(M, 0);

        long long result = 0;

        for (int i = 1; i <= N; i++)

        {

                 int num;

                 cin >> num;

 

                 pSum[i] = (pSum[i - 1] + num) % M; //모듈러 연산 중요

                 if (!pSum[i])

                         result++;

                 //해당 나머지의 개수를 기록

                 cnt[pSum[i]]++;

        }

 

        //각 빈도 f에 대해 fC2를 계산

        for (int i = 0; i < M; i++)

                 result += cnt[i] * (cnt[i] - 1) / 2;

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~