문제 링크
- http://icpc.me/16136
사용 알고리즘
- 세그먼트 트리
풀이
어떤 자연수 N의 약수의 개수는 최대 $O(\sqrt N)$개입니다. $O(\sqrt N)$만에 소수 판별이 가능한 이유를 생각해보면 쉽게 알 수 있습니다.
입력으로 들어오는 수가 최대 100만이므로 6번정도만 약수의 개수로 바꾸는 연산을 해주면 1 또는 2가 됩니다.
구간 합을 구하는 쿼리가 있으니 세그먼트 트리를 생각해봅시다.
구간에 있는 숫자들이 항상 같다는 보장이 없기 때문에 일반적인 방식으로는 세그먼트 트리를 사용하지 못합니다.
그러나 위에서 언급한 것처럼 6번정도만 약수의 개수로 바꾸는 연산을 해주면 1 또는 2가 되기 때문에, 구간에 2보다 큰 원소가 있으면 재귀적으로 들어가 각각 업데이트해주면 됩니다.
한 번의 쿼리는 $O(N)$이 걸릴 수 있지만, 각 원소에 대해 최대 6번 정도의 연산만 하면 되므로 Q개의 쿼리를 다 처리하면 $O(6 Q log N) = O(Q log N)$이 됩니다.