[백준 10986] 나머지 합

 

 

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

10986번: 나머지 합

 

알고스팟의 크리스마스 선물 1번과 동일한 문제이다. (https://algospot.com/judge/problem/read/CHRISTMAS)

(psum[e] - psum[s-1]) mod M = 0
psum[e] mod M == psum[s-1] mod M 

위의 성질을 이용해서 푼다.

 

count에 들어있는 나머지가 같은 횟수끼리 2개를 고르는 조합을 선택하면 되는데

마지막에는 자기자신만을 택해도 m으로 나눠지는 count[0] 값을 더해줘야 한다.

 

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

vector<int> makePSum(const vector<int>& a, int m, int n){
    vector<int> psum(n+1);
    for(int i = 1; i <= n; i++){
        psum[i] = (psum[i-1] + a[i]) % m;
    }
    return psum;
}

long long solve(const vector<int>& psum, int m, int n){
    vector<long long> count(m, 0);
    for(int i = 1; i <= n; i++){
        count[psum[i]]++;
    }
    
    long long result = 0;
    for(int i = 0; i < count.size(); i++){
        if(count[i] >= 2){
            result += ((count[i] * (count[i]-1)) / 2);
        }
    }
    
    // 자기 자신
    result += count[0];
    return result;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    vector<int> a, psum;
    
    cin >> n >> m;
    a.resize(n+1);
    for(int i = 1; i <= n ; i++){
        cin >> a[i];
    }
    
    psum = makePSum(a, m, n);
    cout << solve(psum, m, n) << '\n';
    
    return 0;
}

 

 

아 result는 int 형으로 하면 틀린다~ 범위가 넘어가는 듯.