[알고리즘] 백준 10986 나머지합 // 누적합, 나누기

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

 

* 아이디어 

• % 문제는 분배법칙으로 막 나눠라.

• %m으로 나눈 누적합을 구하라
• 쌍을 찾아 C2 하면 답이다.
• 원래 값이 0인것도 답이다.

 

• 같은 값을 선택한 예시 -> s[4] - s[2] == 원본배열에서 초록칸부분 1,2와 같음
• 즉, 같은값 에서 2개를 선택하는 경우의수 == 정답의 경우의 수

 

 

* 전체코드

• c는 ret를  long long으로 해야함 (파이썬은 정수값 무제한임)

#include <bits/stdc++.h>

using namespace std;

int n, m;
long long arr[1000000 + 4], sum[1000000 + 4];
long long ret;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        long long tmp;
        cin >> tmp;
        arr[i] = tmp;
    }

    // sum을 %m한 결과 구하기
    sum[0] = arr[0] % m ;
    for (int i = 1; i < n; ++i) {
        sum[i] = (sum[i-1]%m + arr[i]%m )%m; // %는 막갈겨라.
    }

    // 값이 0의갯수는 정답에 더하기
    for (int i = 0; i < n; ++i) {
        if (sum[i] == 0) ret++;
    }

    vector<long long> v(m,0); //v[i] : i숫자의 갯수
    // 같은값 갯수세기
    for (int i = 0; i < n; ++i) {
        v[sum[i]]++;
    }

    // C2하기
    for (auto num : v) {
        if (num == 0) continue;
        ret = ret + num* (num - 1) / 2;
    }
    
    cout << ret;

    
    return 0;
}