백준 10986번, 나머지 합 풀이
문제 백준 10986번 풀이 태그는 누적합 문제가 붙어있지만, 저는 수식 정리 연습 문제라고 느꼈습니다. 누적합을 아래와 같이 정의합니다. $$ S(i, j) = \sum_{k=i}^j A[k] $$ (단, $i \leq j$) 한편, $ sum[i] = S(1, i) $의 배열을 만들어두면, 임의의 누적합 $ S(i, j) $에 대하여 $ sum[j] - sum[i - 1] $로 나타낼 수 있으므로 $O(1)$에 구할 수 있습니다. 본격적인 수식 정리를 해보겠습니다. $$ S(i, j) = sum[j] - sum[i - 1] = kM $$ (단, $k$는 자연수) 위 식에서 $M$으로 나눈 나머지를 구해봅시다. * 우변인 $kM$이 항상 $M$의 배수이므로 $M$으로 나눈 나머지는 0이 됩니다. $$ ..
2021.01.23