나머지 합 10986

문제

접근 방법

구간 합을 구하고 2중 루프로 해결하면 될 것 같았다. 물론 당연하게도 시간 초과가 떴다.
순서나 그런 부분에서 규칙이 있을 거 같았고 예제를 조합해서 7이 나오는 경우를 생각해보려 했다.
하지만 방법이 떠오르지 않았다.
그래서 방법을 찾아봤다.

(i까지의 합-j까지의 합) % M=0인 경우는
i까지의 합 % M=j까지의 합 % M이다.
즉 누적 합의 나머지가 같은 것끼리 묶은 뒤 조합을 해주면 되는 것이다.

좀 더 복합적으로 생각해야 풀리는 것 같다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    ll N, M, ret = 0;
    cin >> N >> M;
    vector<ll> prefix, mod(M);
    int num;
    cin >> num;
    prefix.push_back(num);
    for (int i = 1; i < N; ++i)
    {
        cin >> num;
        prefix.push_back(prefix[i - 1] + num);
    }
    for (ll i : prefix)
    {
        int modNum = i % M;
        if (!modNum)
            ++ret;
        ++mod[modNum];
    }
    for (ll i : mod)
        if (i > 1)
            ret += i * (i - 1) / 2;
    cout << ret;
    return 0;
}

풀이

누적 합을 아는가.
나머지 연산의 분배 법칙을 활용할 수 있는가.
조합을 아는가.

이 3가지가 융합된 문제이다.

2중 루프를 간소화할 수 있지 않을까만 생각한 것 같다.
이 문제는 다른 문제보다 수학적 측면이 조금 더 큰 거 같기도 하다.