문제

10986번: 나머지 합

풀이

입력으로 주어지는 수의 개수가 정말 많이 때문에 반복해서 문제를 풀기엔 시간이 모자르다.
따라서 누적합을 활용하여 해결할 수 있다.

문제에서 결과적으로 M으로 나누었을 때의 나머지 부분만을 원하기 때문에 입력으로 어떤 수가 들어와도 % m 연산으로 처리하면 된다.
누접합도 마찬가지로 나머지 부분만을 취한다.
문제의 예시를 예로 들어보면 입력으로 1 2 3 1 2가 주어지면 이를 1 2 0 1 2로 변환할 수 있고 다시 1 3 3 4 6 다시 나눈 나머지를 계산하여 1 0 0 1 0이 된다.

• 1 2 3 1 2
• 1 2 0 1 2
• 1 3 3 4 6
• 1 0 0 1 0

이 변환된 수열의 의미를 잘 알아야 한다.
변환 된 수열의 i번째 수 - j 번째 수 는 입력된 수열의 i+1번째 수 부터 j번째 수의 합의 나머지 값이 된다. 그 합이 나누어 떨어지기 위해 변환된 수열의 i번째 수 - j번째 수 가 0이 되는 경우만을 찾으면 된다. 즉 변환된 수열의 값이 같은 2개의 인덱스를 찾으면 된다.

즉 $_kC_2$를 찾으면 된다. (k는 같은 수의 개수)

이때 0은 특수한 경우로 i와 j가 같아도 성립된다.
따라서 변환된 수열 앞에 0을 임의로 붙여 계산해도 되고,
전부 계산 후 0의 개수만 따로 더해주어도 된다.

변환된 수열의 개수를 세기 위해 숫자의 개수를 센 배열을 만들어 사용하여 최대한 반복을 적게하였다.

결과 값의 최대값이 1000000 * (1000000 - 1) / 2가 될 수 있기 때문에 64비트를 사용하는 자료형에 저장해야 한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
// vector<long long> sequence;
vector<int> count;

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

    cin >> n >> m;
    long long res = 0;
    // sequence.push_back(0);
    count.assign(m, 0);
    count[0] += 1;
    long long input, pre = 0, now;
    for (int i=0; i < n; i++){
        cin >> input;
        // pre = sequence.back();
        now = (pre + input) % m;
        count[now] += 1;
        // sequence.push_back( now );
        pre = now;
    }
    for (int cnt : count){ 
        if ( cnt != 0 ) res += (long long)cnt * (cnt - 1) / 2;
    }
    cout << res << endl;
    return 0;
}