목록오프라인 쿼리 (1)
블로그 옮겼습니다
2017 SCPC 예선 2차 Divisor
\(N,M\le{10^5}\)인덱스 이외의 모든수는 \({10^6}\) 이하의 자연수 N개의 수로 이루어진 A[i] 가 주어지고, M개의 쿼리가 주어지는데 각 쿼리는 b, l, r 로 이루어지며구해야 할 것은 b의 약수들 중에 \(A_l, A_{l+1}, \dots, A_r\) 들을 모두 나눌 수 없는 약수들의 수 이다.이 각 쿼리들의 결과를 모두 합한 값을 출력하는 문제이다.어차피 각 수는 10^6 이하이기 때문에 이런 배열을 하나 만들 수 있다.last[i] : i로 나눌 수 있는 최대 인덱스그럼 오프라인으로 각 쿼리를 r 로 오름 차순 정렬한뒤 하나하나 봐주면서 현재 쿼리의 r까지 A[i]의 약수들에 대해 last[약수] 를 i로 업뎃해준다. 그런뒤 b의 약수들에 대해 last[약수] 가 l보다 크..
Algorithm/Problem Solving
2017. 9. 10. 12:16