준하의 정수론 과제 (Divmaster)
면접 대비시간 제한1초메모리 제한256 MB
N개의 자연수에 대해 구간의 모든 수를 약수 개수로 바꾸는 작업과 구간 합 출력 작업을 Q번 처리한다. 약수 개수 연산이 빠르게 수렴하는 성질을 이용해 구간마다 방문을 건너뛴다.
문제
준하는 3학년 2학기 때 들으려던 정수론을 수강신청 실수로 2학년 1학기에 듣게 되었다. 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 내고, 모두 풀지 못하면 F학점을 주겠다고 했다. 3학년 사이에서 멘탈이 나간 준하가 학점을 받을 수 있도록 코딩으로 과제를 해결해 주자.
준하가 짜려던 코드는 다음과 같다.
N개의 수에 대해 Q번의 작업을 처리하는데, 작업은 두 가지다.
- 1 S E : S번째 수부터 E번째 수까지 모두 각 수의 약수의 개수로 바꾼다.
- 2 S E : S번째 수부터 E번째 수까지의 합을 출력한다.
입력
첫 번째 줄에 수의 개수 N, 작업의 개수 Q가 주어진다. (1 ≤ N, Q ≤ 100,000)
두 번째 줄에 N개의 자연수 a1, a2, ... aN이 주어진다. (1 ≤ ai ≤ 1,000,000)
다음 Q개의 줄에는 각각 작업을 뜻하는 자연수 T S E가 주어진다. (1 ≤ T ≤ 2, 1 ≤ S ≤ E ≤ N)
출력
2번 작업에 대한 출력을 한 줄에 하나씩 출력한다.