[c++] 백준 10986 나머지 합

10986 나머지 합(acmicpc.net)

 

어떤 수열의 부분합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제이다.

 

모든 부분합에 대해서 경우의 수를 세어주면 O(N²)의 시간에 해결할 수 있다.

하지만 N의 범위가 10⁶까지 이므로

이 시간 복잡도로는 문제를 해결할 수 없다.

 

A의 누적합 배열을 prefix라 하고

잘 생각해 보면 우리가 원하는 경우는

(prefix[j] - prefix[i-1])%m == 0인 경우이다. (i <= j)

 

이를 풀어보면

prefix[j]%m - prefix[i-1]%m == 0

prefix[j]%m == prefix[i-1]%m

을 얻을 수 있다.

 

서로 나머지가 같은 것을 선택하면 서로 상쇄하기 때문에

(부분합을 구할때 prefix[j] - prefix[i-1] 를 하는 것을 생각해보면 이해가 쉽다)

m으로 나눈 나머지가 0인 부분합임을 알 수 있다.

 

그렇다.

m으로 나눈 나머지가 같은 경우를 짝지으면 그것이 경우 하나가 되는 것이다.

만약 m으로 나눈 나머지가 같은 것이 k개가 있다 하면

_kC₂ = k*(k-1)/2 만큼의 경우가 발생하는 것이다.

 

m으로 나눈 나머지이니 나머지의 종류는 0~m-1까지 발생한다.

문제에서 m은 1000까지라 주어졌으므로

이는 충분히 지지고 볶기 좋은 범위이다.

 

따라서 A의 누적합을 m으로 나눈 나머지를 카운트해 주고

이를 Combination으로 계산한 결과를 모두 더해주면 답을 구할 수 있다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,pf,ans,mod[1010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(ll i=1; i<=n; i++){
        ll k; cin>>k;
        pf = (pf+k)%m;
        mod[pf]++;
    }
    for(ll i=0; i<m; i++)
        ans += mod[i]*(mod[i]-1)/2;
    cout << ans+mod[0];
}

 

※ 주의사항

- A의 원소의 범위가 매우 커서

누적합을 진행하다 보면 int자료형을 넘는다.

long long을 사용해 주자

- 마지막에 mod[0]을 더해줘야 한다.

다른 요소들은 서로 쌍을 이루며 상쇄되기 때문에 따로 더하지 않지만

0은 처음부터 0이기 때문이다.