[BOJ] 10986번: 나머지 합

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

sum[i]를 A[1] to A[i]의 합이라고 할 때, A[i] + A[i+1] + ... + A[j] = sum[j]-sum[i-1]로 표현할 수 있습니다.

문제를 바꾸어 생각하면 sum[j]-sum[i-1]이 M으로 나누어 떨어지는 (i,j)의 쌍 수이고, 이는 곧 sum[0 to N]을 M으로 나눈 나머지가 각각 몇개씩 있는지에 따라 값을 쉽게 알아낼 수 있습니다.

문제의 예시인 1 2 3 1 2의 경우, sum은 0 1 3 6 7 9이고 3으로 나눈 나머지가 0인 것은 4개, 1인 것은 2개, 2인 것은 0개이므로 4 combination 2 + 2 combination 2가 정답입니다.

https://github.com/blisstoner/BOJ/blob/master/10986.cpp