백준 10986 - 나머지 합

백준 10986 - 나머지 합

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

풀이

N의 최대값이 $10^6$ 이며, 이 수에 대하여 모든 구간 합을 구해야 하므로

시간 제한에 걸린다. 구간 합 배열을 구하고, 구간 합 배열을 M 으로 나눈

나머지를 저장하는 배열을 만든다. 나머지를 저장한 배열에서 원소 값이 0인 것은

즉, 원본 배열의 0부터 i까지의 구간 합이 M으로 나누어 떨어진다는 것이다.

또한 중간 구간의 계산값에서도 구해야 한다.

$ (Sum[j] - Sum[i]) \; \% \; M = 0 $ 인 구간을 구해야 하는데 이는,

$ Sum[j] \; \% \; M = Sum[i] \; \% \; M $ 과 같다.

따라서 나머지를 저장한 배열에서 원소 값이 같은 인덱스의 개수를 세주면 된다.

코드