나머지 합

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

연속된 부분의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제

 

나머지 연산

(A - B) % C = ((A % C) - (B % C)) % C와 같다

 

즉, 구간 합 배열의 원소를 m으로 나눈 나머지로 업데이트하고

s[i]와 s[j]가 같은 쌍을 찾자.

그럼 (s[j] - s[i]) % m은 0이다.

 

그럼 원본 배열에서 i + 1부터 j까지의 구간합이

M으로 나누어 떨어지는 구간

 

나머지가 0이 나오면 0부터 i까지의

구간 합 자체가 나누어 떨어지므로

정답에 더해준다.

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m;
    cin >> n >> m;
 
    // 범위가 크므로
    vector<long> s(n, 0);// 여기에 n을 넣어서 틀렸었다...
    vector<long> c(m, 0);
    long answer = 0;
    cin >> s[0];
 
    for (int i = 1; i < n; i++)
    {
        int tmp = 0;
        cin >> tmp;
        s[i] = s[i - 1] + tmp;
    }
 
    for (int i = 0; i < n; i++)
    {
        int remainder = s[i] % m;
 
        // 0 ~ i까지의 구간 합 자체가 0일 때 정답에 더하기
        if (remainder == 0)
            answer++;
        
        // 나머지가 같은 인덱스의 개수 세기
        c[remainder]++;
    }
 
    // 나머지니까 0 ~ m -1이겠지
    for (int i = 0; i < m; i++)
    {
        // 1보다 크다면 C(n, 2) 해준다.
        // n * (n - 1) / 2
        if (c[i] > 1)
        {
            answer += (c[i] * (c[i] - 1) / 2);
        }
    }
    cout << answer << '\n';
}