10986. 나머지 합
·
PS/Baekjoon
📜 문제 설명N개의 숫자가 주어질 때, 연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수배열 [1, 2, 3, 1, 2]에서 3으로 나누어 떨어지는 구간?👉 [1, 2], [1, 2, 3], [3], [2, 3, 1], [3, 1, 2], [1, 2] = `7개`N: 숫자 개수 (N ≤ 백만)M: 나누는 수 (M A₁ 숫자가 백만 개까지 주어질 수 있어서 `O(NLogN) 이하`의 시간 복잡도로 풀어야 시간 초과가 나지 않는다.부분 구간의 개수를 구해야 하므로 계산 할 때마다 합을 구해 나가는 게 아닌, `누적합`을 이용해 풀어야 한다.M으로 나누어 떨어지는, 즉 M으로 나눈 나머지가 0인 구간을 구하려면 `(A+B) % M == 0` 수식으로 풀면 된다.📌 나머지 연산(A+B)%C 는 {..