[BAEKJOON] 10986 나머지의 합

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int main() {     int n, m;     scanf("%d %d", &n, &m);       vector<int>map(1000001);     for (int x = 0; x < n; x++)     {         scanf("%d", &map[x]);         map[x] %= m;     }       vector<long long>cnt(1001,0);     int sum = 0;       cnt[0] = 1;     for (int x = 0; x < n; x++)     {         sum += map[x];         sum %= m;         cnt[sum] += 1;     }       long long answer = 0;     for (int x = 0; x < m; x++)         answer += (cnt[x] * (cnt[x] - 1)) / 2;       printf("%lld", answer);     return 0; }

더해서 나머지가 같은 것들만 모아 놓는다

모아놓은 것 중에 2개를 골라서 빼면 나머지가 0인 합을 찾을 수 있다

그것은 nC2이기 때문에 마지막에 ((n)(n-1))/2 를 계산하는 것이다.

이 문제는 너무 어려웠다..