← 返回题目

题库练习求和与替换

← 上一题下一题 →

A6897 | $求和与替换$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

设 $D(x)$ 表示正整数 $x$ 的正约数个数。例如，$D(2)=2$（$2$ 能被 $1$ 和 $2$ 整除），$D(6)=4$（$6$ 能被 $1$、$2$、$3$ 和 $6$ 整除）。 给定一个包含 $n$ 个整数的数组 $a$。你需要处理两种类型的操作： 1. REPLACE $l$ $r$：对于每一个 $l\le i\le r$，将 $a_i$ 替换为 $D(a_i)$； 2. SUM $l$ $r$：计算 $\sum_{i=l}^{r} a_i$。 每次 SUM 操作需要输出结果。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 3\cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^6$）。 接下来 $m$ 行，每行包含 $3$ 个整数 $t_i,l_i,r_i$： - 若 $t_i=1$，表示 REPLACE $l_i$ $r_i$ - 否则表示 SUM $l_i$ $r_i$ 保证至少有一次 SUM 操作。

输出格式

对于每个 SUM 操作，输出一行结果。

输入输出样例

输入 #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

C++ 编辑器

输入

输出