[10986번] 나머지 합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

2. Prefix Sum :: http://www.crocus.co.kr/search/Prefix Sum

아래 수식을 이해해보자.

Ai에서 Aj까지 합은 Sj에서 S(i-1)을 뺀 것과 같다.

이때 문제에서 총합의 나머지가 m과 같아야 한다 했으니 결국 좌변의 합에 % m을 한 것과 우번의 합에 % m을 한것이 같아야 한다.

따라서 Sj % m = S(i-1) % m임을 알 수 있다.

그렇다면 어떤 작업을 해야할까?

1. Prefix Sum 알고리즘을 통해 모든 구간 합을 구한다.

2. 구간 합들의 나머지를 나머지 배열에 넣어둔다.(해당하는 인덱스가 나머지를 의미하도록)

3. 조합론을 생각하며 를 해준다.(이 의미는 해당하는 같은 나머지 2개를 뽑아서 조합한다는 의미이다.)

소스 코드 : 

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 35 36 37

#include <iostream> #include <cstdio>   using namespace std;   int arr[1000002]; int mod[1001];   int main() {     int n, m;     scanf("%d %d", &n, &m);          for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       long long sum = 0;     mod[0] = 1;     for (int i = 0; i < n; i++)     {         sum += arr[i];         sum %= m;           mod[sum]++;     }       long long ans = 0;     for (int i = 0; i < m; i++)         ans += (long long)mod[i] * (long long)(mod[i]-1) / 2;       printf("%lld", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus