문제 링크
- http://icpc.me/10986
사용 알고리즘
- Prefix Sum
시간복잡도
- O(N)
풀이
Update 쿼리가 없고, 연속된 구간의 합에 관련된 쿼리문제이므로 prefix sum을 먼저 생각해볼 수 있습니다.
구간의 합을 M으로 나눈 나머지가 0인 구간의 개수를 세야 합니다.
시작점과 끝점을 잡고 돌리면 O(N2)이기 때문에 TLE가 뜹니다. 최적화시킬 아이디어를 찾아야 합니다.
입력 예제로 주어진
1 |
|
의 누적합을 구하면 1 3 6 7 9 입니다. 3으로 모듈러 연산을 하면 1 0 0 1 0 이 나옵니다.
모듈러 연산의 성질을 다시 한 번 생각해봅시다.
(A + B) % C와 (A%C + B%C) % C의 결과는 동일합니다. 덧셈 뿐만 아니라 뺄셈, 곱셈에 대해서도 성립합니다.
다시 문제로 돌아와서, [i, j] 구간의 합은 sum[j] - sum[i-1] 이고, 문제에서는 (sum[j] - sum[i-1]) % M 이 0인 순서쌍 (i, j)의 개수를 묻고 있습니다.
(sum[j] - sum[i-1]) % M = 0 이라면 (sum[j]%M) - (sum[i]%M) = 0 입니다.
이 점을 활용해서 sum[i]%M = sum[j]%M 인 쌍의 개수를 구해주면 됩니다.
그러나 sum[x]%M = 0 인 경우에는 자기 혼자만으로도 나누어 떨어지는 구간이 되기 때문에 sum[x]%M == 0 인 경우는 따로 카운팅해야 합니다.
전체 코드
1 |
|