[백준][C++] 10986: 나머지 합

문제

풀이

수학, 누적 합 문제이다.

 

N이 1000,000이므로 완전 탐색시 O(N * N)으로 시간초과이다.

 

(A - B) % n = ((A % n) - (B % n) + n) % n

• 배열의 i번째 수까지의 누적 합을 sum이라고 하자. 임의의 j번째에서 k번째 까지(j <= k < i)의 누적 합을 x라고 하자.
• (sum - x) % M == 0인 경우 답을 만족하므로, ((sum % M) - (x % M) + M) % M == 0을 만족해야 한다.
• 즉, (sum % M) == (x % M)인 x의 수가 i번째 탐색에서 답에 추가된다.
• sum % == 0인 경우에는 sum자체도 답에 추가된다.

코드

#include <iostream>

using namespace std;

// 현재까지 나온 수 중에서 mod연산의 결과가 index인 것의 수를 담는다.
// M이 1000이하이므로 최대 나머지는 999이다.
int mod[1000];

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

    int N, M;
    cin >> N >> M;

    // 지금까지의 합인 sum
    // (sum - x) % M == 0인 경우에 답을 만족하므로,
    // ((sum % M) - (x % M) + M) % M == 0을 만족해야 한다.
    // 즉, sum % M == x % M인 x의 수가 answer에 추가된다. 
    // sum % == 0인 경우에는 sum자체도 answer에 추가되야 한다.
    long long answer = 0;
    long long sum = 0;
    for (int i = 0; i < N; ++i)
    {
        long long temp;
        cin >> temp;

        sum += temp;

        answer += mod[sum % M];
        if (sum % M == 0)
        {
            answer++;
        }

        mod[sum % M]++;
    }

    cout << answer;

    return 0;
}