BOJ) 10986 - 나머지 합

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

10986번: 나머지 합

수의 갯수와 범위가 크기 때문에 Prefix Sum 방식을 통해 풀이하였습니다.

 

- S[i] : A[1] ~ A[i] 까지의 합의 나머지

- MODS[K] : 나머지가 K인 S[i]의  갯수

 

i<=j 일 때, A[i]+ ...+ A[j] 구간 합을 M으로 나눈 나머지가 0인 경우는 S[j] - s[i-1]가 0인 경우와 같다.

MODS 배열을 이용하여 나머지가 같은 (S[j] = S[i-1]) 모든 쌍의 수를 구해주면 된다.

---

C++ 소스 코드

#include <iostream>
using namespace std;
int s[1000001];
long long mods[10001];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    long long ans=0;
    cin >> n >> m;
    int temp,mod;
    mods[0]=1;
    for(int i=1;i<=n;i++){
        cin >> temp;
        s[i] = s[i-1]+temp;
        // s[i] : a[1] ~ a[i] 합의 나머지
        s[i]%=m;
        mods[s[i]]++;
    }
    for(int i=0;i<m;i++){
        //나머지가 같은 쌍 전부 추가
        ans+= mods[i]*(mods[i]-1)/2;
    }
    cout << ans << '\n';
    return 0;
}