생일 케이크 나누기
실버 V의견: 0
리세 베이커리에서 생일 파티를 위해 케이크를 \(N\)조각으로 잘랐다. \(i\)번째 조각에는 \(a_i\)개의 딸기가 올라가 있다.
파티 참가자들은 총 \(Q\)번의 질문을 한다. 각 질문은 정수 \(l\), \(r\)로 이루어지며, '\(l\)번째부터 \(r\)번째까지의 조각에 있는 딸기 수의 합을 \(M\)으로 나눈 나머지'를 묻는다.
각 질문에 답하여라.
- \(1 \le N, Q \le 100\,000\)
- \(2 \le M \le 10^9\)
- \(0 \le a_i \le 10^9\)
- \(1 \le l \le r \le N\)
첫째 줄에 조각의 수 \(N\), 나누는 수 \(M\), 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 조각의 딸기 수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문 \(l\), \(r\)이 공백으로 구분되어 한 줄에 하나씩 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문의 답을 순서대로 출력한다.
5 10 3
3 7 2 8 5
1 3
2 5
1 5
2
2
5
구간 \([1,3]\)의 합은 \(3+7+2=12\)이고 \(12 \bmod 10 = 2\)이다. 구간 \([2,5]\)의 합은 \(7+2+8+5=22\)이고 \(22 \bmod 10 = 2\)이다. 구간 \([1,5]\)의 합은 \(25\)이고 \(25 \bmod 10 = 5\)이다.
4 10 3
10 10 10 10
1 4
1 1
2 3
0
0
0
모든 조각이 \(10\)이고 \(M=10\)이므로 어떤 구간의 합을 \(10\)으로 나눠도 나머지는 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
생일 케이크 나누기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
생일 케이크 나누기