백준 10986번 나머지 합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

문제풀이

사용한 알고리즘: 수학

(1) 생각

 연속합이 modulo M 에서 0인 구간을 찾는 문제입니다.
 (A_1 ~ A_x 의 연속합)%M 을 map으로 종류별 개수로 모두 저장합니다.
 : map< 연속합%M , 개수 >
 A_1~A_a = t , A_1~A_b = t 로 같다면, A_a~A_b 의 연속합은 0임을 생각할 수 있습니다.

(2) 코드 14~22

 [연속합%M] 의 개수들을 저장해줍니다.
 이때 연속합%M=0 이면 그 구간 자체로 정답이 되는걸 생각해줍니다.

(3) 코드 23~26

 조합(combination) 을 생각해주면 됩니다.
 과정(1) 에서 언급한 것 처럼 연속합%M의 값이 같은 구간 2개를 고르는 경우수를 구합니다.
 연속합%M 의 개수가 X 라면, 그 개수는 X C 2 = X * (X-1) /2 입니다.