10986

나머지 합

문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

책-74쪽에 상세한 설명 기재

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<long long> v(n + 1, 0);
    vector<long long> c(m, 0);

    for (int i = 1; i <= n; i++)
    {
        int temp;
        cin >> temp;
        v[i] = v[i - 1] + temp;
    }

    long long answer = 0;

    for (int i = 1; i <= n; i++)
    {
        int remainder = v[i] % m;

        if (remainder == 0)
            answer++;

        c[remainder]++;
    }

    for (int i = 0; i < m; i++)
    {
        if (c[i] > 1)
            answer += c[i] * (c[i] - 1) / 2;
    }

    cout << answer;
}