백준 10986번 나머지 합 - C++(cpp) 풀이

---

 

1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면, psum[e] % M = psum[s-1] % M이어야 한다.
2. psum[i] % M = psum[j] % M 인 (i, j) 쌍의 개수를 구한다.
3. psum[i] % M 자체가 0인 경우도 추가로 카운트한다.

 

1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면,psum[e] % M = psum[s-1] % M이어야 한다.

 i까지의 누적합을 psum[i]라고 하자. s부터 e까지의 구간합은 psum[e] - psum[s-1]이 된다. 이 구간합이 M으로 나누어 떨어지려면, (psum[e] - psum[s-1]) % M = 0이어야하므로, psum[e] % M = psum[s-1] % M이 성립해야 한다.

 

2. psum[i] % M = psum[j] % M 인 (i, j) 쌍의 개수를 구한다.

 따라서 psum[i] % M = psum[j] % M인 (i, j)쌍의 개수를 구하면 된다. (단, i < j)

 

3. psum[i] % M 자체가 0인 경우도 추가로 카운트한다.

 2에서 구한 i, j 쌍에서 i는 0 이상이므로 s=0인 구간은 고려하지 않았다. s=0인 경우의 구간합은 psum[e] 자체이므로 psum[i] % M = 0인 경우도 카운트해주어야 한다.

반응형

---

#include <iostream>

using namespace std;

typedef long long ll;

const int MAX = 1000001;

int N, M;
ll arr[MAX], psum[MAX], cnt[1000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=1; i<=N; i++) {
        cin >> arr[i];
        psum[i] = (psum[i-1] + arr[i]) % M;
        cnt[psum[i]]++;
    }
    
    ll ans = 0;
    for (int i=0; i<M; i++) ans += cnt[i] * (cnt[i] - 1);
    ans /= 2;
    ans += cnt[0];
    
    cout << ans;

    return 0;
}