%2021. 12. 6. 05:11에 작성된 글입니다%
16136번: 준하의 정수론 과제 (Divmaster)
준하는 3학년 2학기 때 들으려고 했던 정수론을 수강신청을 잘못하는 바람에 2학년 1학기 때 신청하고 말았다! 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 던지고, 이 문제
www.acmicpc.net
Divmaster가 무슨 뜻일까? 해당 div에서 가장 어려운 문제였다는 말일까?
아무튼 쿼리 처리하는 문제다. 쿼리 모양새를 보니 세그트리를 쓰면 좋을 것 같다.
일단 에라토스테네스의 체를 약간 응용해서 \(1\)~\(10^6\)까지 약수의 개수를 구할 수 있다. 이거 어디 담아놓고서 나중에 필요할 때 꺼내먹으면 된다.
노드는 구간의 합과 died라는 이름의 bool 변수를 갖게 했다. 이게 값이 \(2\)나 \(1\)인 경우에는 더 이상 갱신이 이루어지지 않기 때문에 특정 구간이 \(2\)나 \(1\)로만 이루어져 있다면 갱신할 때 들어갈 필요가 없다. (들어갔다? 이제 TLE. ㅅㄱ)
리프 노드인데 값이 \(2\)보다 작다? 죽이고, 니 자식 노드 다 죽었어? 그럼 너도 죽이고...