[BOJ/백준][Gold4] 10986: 나머지 합(C++)

 

www.acmicpc.net/problem/10986

10986번: 나머지 합

 

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고
만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

 

#include <cstdio>
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<M;i++){
        int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10986.cpp