시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB66817413128.603%

문제

준하는 3학년 2학기 때 들으려고 했던 정수론을 수강신청을 잘못하는 바람에 2학년 1학기 때 신청하고 말았다! 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 던지고, 이 문제들을 모두 풀지 못한 사람에게는 F학점을 주겠다는 끔찍한 소리를 하였다. 3학년들의 틈에서 멘탈이 나간 준하가 학점을 받을 수 있도록 코딩으로 과제를 해결해주자!

준하가 짜려고 했던 코드는 다음과 같다.

N개의 수에 대해서 Q번의 작업을 처리하는데, 작업은 2가지로 이루어져 있다.

  • 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번 작업에 대한 출력을 한 줄에 하나씩 출력한다.

서브태스크 1 (3점)

  • T = 1

서브태스크 2 (17점)

  • N ≤ 1,000
  • Q ≤ 1,000

서브태스크 3 (24점)

  • T = 2

서브태스크 4 (56점)

  • 추가 제한 없음

예제 입력 1

7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7

예제 출력 1

30
13
4
22

출처

High School > 서울과학고등학교 > SciOI 2018_01 G번

채점 및 기타 정보

  • 예제는 채점하지 않는다.