정수 M으로 나누어 떨어지는 부분 구간합을 선형시간에 구하는 놀라운 방법

1. 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 2. 풀이 누적합이야 prefix sum 방법으로 O(N)에 미리 구해놓고 [i,j]의 구간합은 O(1)에 구할 수 있는데 정수 M으로 나누어 떨어지는 구간합 [i,j]를 어떻게 하면 아주 빠르게 구할 수 있을까 가장 쉬운 방법은 모든 i,j에 대해 검사하는 이중 for문 방법이지만 N이 $10^{6}$이다 보니 $O(N^{2})$으로는 1초안에 통과할 수..