백준 10986 (나머지 합) C++

문제

10986번: 나머지 합

배열 A(1) ~ A(n) 까지 주어지면 임의의 구간 [i, j] (A(i)+ ~ +A(j))에서의 합이 m으로 나누어 떨어지는 

(i, j) 쌍의 개수를 구는 문제 입니다.

 

단순히 prefix sum을 이용해서 구간의 합인 [i, j]를 구하기 위해 prefixsum[j] - prefixsum[i-1]을 하게 되면

끝점 j를 잡고 이중 for문을 돌리게 되면 시간 복잡도가 O(n^2)이 나와서 시간초과가 나오게 됩니다.

 

따라서 조금더 효율적인 방안을 생각해 보아야 합니다.

나머지 정리를 활용하면 어떤수 A, B에 대해서 (A+C) % m = (A%C + B%C) % m 입니다.(덧셈, 뺄셈, 곱셈 모두 적용)

우리가 구하고자 하는 식은 (prefixsum[j] - prefixsum[i]) % m = 0 인 경우의 수를 찾는 것입니다.

이를 정리하면 prefixsum[j] % m - prefixsum[i] % m = 0 

prefixsum[j] % m = prefixsum[i] % m 인 것을 찾는 것입니다.

즉, 나머지가 같은것들을 세어주고 조합을 통해 nC2 를 해주면 됩니다.

그리고 prefixsum[x] % m = 0 인 경우 단순히 1 부터 x까지 의 합이 0이기 때문에 따로 세어줘야 합니다.

예를 들어 arr = {1, 2, 3, 1, 2} 이고 m = 3 인경우 표는 다음과 같습니다.

Index	1	2	3	4	5
arr[]	1	2	3	1	2
prefix sum[]	1	3	6	7	9
prefixsum % m	1	0	0	1	0

나머지가 0인것이 3개 있으므로 3C2 = 3

나머지가 1인것이 2개 있으므로 2C2 = 1

마지막으로 단순히 Prefix sum % m이 0인경우 = 3

다 더하면 3 + 1 + 3 = 7 이 됩니다.

 

int n, m;
cin >> n >> m;
vector<ll>cnt(m,0);
ll prefix = 0;
for (ll i = 0, a; i < n; i++) {
    cin >> a;
    prefix += a;
    prefix %= m;
    cnt[prefix]++; //나머지가 같은 것을 세어줌
}
ll ans = cnt[0];
for (int i = 0; i < m; i++)
    ans += cnt[i] * (cnt[i] - 1) / 2; // nC2
cout << ans;
 

3번째 줄을 보면 cnt배열을 통해 나머지가 같은것을 세어줍니다.

m으로 나누어 주기 때문에 나머지는 m보다 클 수 없습니다. 따라서 벡터의 공간은 m으로 잡아주었습니다.

11번째 줄을 보면 prefix sum % m = 0 인 경우 다 세어줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ll>cnt(m,0);
    ll prefix = 0;
    for (ll i = 0, a; i < n; i++) {
        cin >> a;
        prefix += a;
        prefix %= m;
        cnt[prefix]++; //나머지가 같은 것을 세어줌
    }
    ll ans = cnt[0]; // prefixsum % m = 0 인 경우
    for (int i = 0; i < m; i++)
        ans += cnt[i] * (cnt[i] - 1) / 2; // nC2
    cout << ans;
 
    return 0;
}