(C++) - 백준(BOJ) 10986번 : 나머지 합

#include <iostream>
#include <cstring>
using namespace std;
 
//a[i]+....+a[j] = sum[j] - sum[i-1]
//(a[i]+....+a[j])%M = (sum[j] - sum[i-1])%M
//s[i]%m = s[j]%m인 부분을 찾으면 된다.
//cnt[k] => (s[i]%m == k) 인 i의 개수
//cnt[i] * (cnt[i]-1) / 2의 합이 쌍의 개수이다
 
int main() {
    long long n;
    long long m;
    long long ans = 0;
    cin >> n >> m;
 
    long long *a = new long long [n + 1];
 
    long long sum = 0;
    long long *cnt = new long long[m];
 
    memset(a, 0, sizeof(long long));
    for (long long i = 0; i < m; i++)
        cnt[i] = 0;
    cnt[0] = 1;
 
    for (long long i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] %= m;
        sum += a[i];
        sum %= m;
        cnt[sum]++;
    }
 
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            if ((sum[j] - sum[i - 1]) % m == 0)
                ans++;
        }
    }*/ //n^2시간이기에 무조건 시간 초과다
 
 
 
    for (long long i = 0; i < m; i++)
    {
        ans += cnt[i] * (cnt[i] - 1) / 2;
    }
 
    cout << ans << '\n';
 
}