나머지 합 - 10986번

해결방법

1. SUM(0 ~ i) % M의 개수를 받는다.
2. i <= k <= j (단, i <= j , j < M) 까지 2개를 선택하는 경우의 수를 더해준다.

소스코드

#include<iostream>
using namespace std;
typedef long long ll;
ll num[1000001], N, M;
int main() {
    ll sum = 0, a;
    cin >> N >> M;
    while(N--) {
        cin >> a;
        sum += a;
        num[sum % M]++;
    }
    ll ans = num[0];
    for (int i = 0; i < M; ++i)
        ans += (num[i] * (num[i] - 1)) / 2;
    cout << ans;
    return 0;
}