백준 10986번 나머지 합

문제 링크

$mod$ $m$ 하면서 누적합 구해주고, 나머지가 같은 $i, j$를 선택해서 잘라주면 된다. 오버플로우 조심.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

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

    int n, m;
    cin >> n >> m;
    vector<int> v(n), psum(n);

    for (auto& x : v) {
        cin >> x;
    }

    psum[0] = v[0] % m;

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

    vector<int> mcnt(m);
    for (auto x : psum) {
        mcnt[x]++;
    }
    mcnt[0]++;

    ll ans = 0;
    for (auto x : mcnt) {
        ans += (ll)x*(x-1)/2; // overflow
    }

    cout << ans;

    return 0;
}