Li Hua and Array

题意翻译

给定一个长度为 $1\le n\le 10^5$ 的数列，$1\le a_i\le 5\times 10^6$。 有 $m\le 10^5$ 次操作 `o l r`， 1. $o=1$ 时， $\forall\ l\le i\le r$，$a_i\gets\varphi(a_i)$ 2. $o=2$ 时，找出使 $a_l=a_{l+1}\dots=a_r$ 的最小变化。在每次变化中，选择一个 $x\in[l,r],a_i\gets \varphi(a_i)$。修改独立。 对于每个操作 $2$ 输出最小答案。

题目描述

Li Hua wants to solve a problem about $ \varphi $ — Euler's totient function. Please recall that $ \varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1] $ . $ ^{\dagger,\ddagger} $ He has a sequence $ a_1,a_2,\cdots,a_n $ and he wants to perform $ m $ operations: - "1 $ l $ $ r $ " ( $ 1\le l\le r\le n $ ) — for each $ x\in[l,r] $ , change $ a_x $ into $ \varphi(a_x) $ . - "2 $ l $ $ r $ " ( $ 1\le l\le r\le n $ ) — find out the minimum changes needed to make sure $ a_l=a_{l+1}=\cdots=a_r $ . In each change, he chooses one $ x\in[l,r] $ , change $ a_x $ into $ \varphi(a_x) $ . Each operation of this type is independent, which means the array doesn't actually change. Suppose you were Li Hua, please solve this problem. $ ^\dagger $ $ \gcd(x,y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ . $ ^\ddagger $ The notation $ [\textrm{cond}] $ equals $ 1 $ if the condition $ \textrm{cond} $ is true, and $ 0 $ otherwise.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1\le n,m\le 10^{5} $ ) — the number of elements in the array and the number of operations to process, respectively. The second line contains $ n $ integers $ a_{1},a_{2},\cdots ,a_{n} $ ( $ 1\le a_{i}\le 5\cdot 10^{6} $ ) — the elements of the array. Next $ m $ lines, each line contains three integers $ t_{i},l_{i},r_{i} $ ( $ t_i\in\{1,2\},1\le l_i\le r_i\le n $ ) — the $ i $ -th operation.

输出格式

For each "2 $ l $ $ r $ ", output the answer in an separate line.

输入输出样例

输入样例 #1

5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4

输出样例 #1

10
2
1

说明

Denote $ \varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases} $ . At first, $ a=[8,1,6,3,7] $ . To make sure $ a_1=a_2=a_3=a_4=a_5 $ , we can change $ a $ to $ a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1] $ , using $ 3+0+2+2+3=10 $ changes. To make sure $ a_3=a_4 $ , we can change $ a $ to $ a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7] $ , using $ 0+0+1+1+0=2 $ changes. After "1 $ 1 $ $ 3 $ ", $ a $ is changed to $ a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7] $ . To make sure $ a_3=a_4 $ , we can change $ a $ to $ a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7] $ , using $ 0+0+0+1+0=1 $ change.

题目大意：
李华想要解决一个关于欧拉函数 $\varphi$ 的问题。给定一个长度为 $1 \le n \le 10^5$ 的数列 $a_1, a_2, \cdots, a_n$，其中 $1 \le a_i \le 5 \times 10^6$。有 $m \le 10^5$ 次操作，每次操作包含一个操作类型 $o$ 和两个索引 $l, r$，操作分为两种：

1. 当 $o=1$ 时，对于所有 $l \le i \le r$，将 $a_i$ 更新为 $\varphi(a_i)$。
2. 当 $o=2$ 时，找出使 $a_l = a_{l+1} = \cdots = a_r$ 的最小变化次数。每次变化可以选择一个 $x \in [l, r]$，并将 $a_x$ 更新为 $\varphi(a_x)$。每次操作独立，即原数列不实际改变。

对于每个操作 $2$，输出最小答案。

输入输出数据格式：
输入格式：
- 第一行包含两个整数 $n$ 和 $m$，分别表示数列的元素个数和要处理的操作数。
- 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示数列的元素。
- 接下来的 $m$ 行，每行包含三个整数 $t_i, l_i, r_i$，表示第 $i$ 个操作。

输出格式：
- 对于每个操作 $2$，输出一行表示答案。

输入输出样例：
输入样例 #1:
```
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4
```
输出样例 #1:
```
10
2
1
```
说明：
- $\varphi^k(x)$ 定义为：当 $k=0$ 时，$\varphi^k(x) = x$；当 $k > 0$ 时，$\varphi^k(x) = \varphi(\varphi^{k-1}(x))$。
- 在第一次操作 $2$ 中，为了使 $a_1 = a_2 = a_3 = a_4 = a_5$，我们可以将数列 $a$ 变为 $a' = [1, 1, 1, 1, 1]$，需要 $10$ 次变化。
- 在第二次操作 $2$ 中，为了使 $a_3 = a_4$，我们可以将数列 $a$ 变为 $a' = [8, 1, 2, 2, 7]$，需要 $2$ 次变化。
- 在操作 $1$ 后，数列 $a$ 变为 $a = [4, 1, 2, 3, 7]$。
- 在第三次操作 $2$ 中，为了使 $a_3 = a_4$，我们可以将数列 $a$ 变为 $a' = [4, 1, 2, 2, 7]$，需要 $1$ 次变化。题目大意： 李华想要解决一个关于欧拉函数 $\varphi$ 的问题。给定一个长度为 $1 \le n \le 10^5$ 的数列 $a_1, a_2, \cdots, a_n$，其中 $1 \le a_i \le 5 \times 10^6$。有 $m \le 10^5$ 次操作，每次操作包含一个操作类型 $o$ 和两个索引 $l, r$，操作分为两种： 1. 当 $o=1$ 时，对于所有 $l \le i \le r$，将 $a_i$ 更新为 $\varphi(a_i)$。 2. 当 $o=2$ 时，找出使 $a_l = a_{l+1} = \cdots = a_r$ 的最小变化次数。每次变化可以选择一个 $x \in [l, r]$，并将 $a_x$ 更新为 $\varphi(a_x)$。每次操作独立，即原数列不实际改变。 对于每个操作 $2$，输出最小答案。 输入输出数据格式： 输入格式： - 第一行包含两个整数 $n$ 和 $m$，分别表示数列的元素个数和要处理的操作数。 - 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示数列的元素。 - 接下来的 $m$ 行，每行包含三个整数 $t_i, l_i, r_i$，表示第 $i$ 个操作。 输出格式： - 对于每个操作 $2$，输出一行表示答案。 输入输出样例： 输入样例 #1: ``` 5 4 8 1 6 3 7 2 1 5 2 3 4 1 1 3 2 3 4 ``` 输出样例 #1: ``` 10 2 1 ``` 说明： - $\varphi^k(x)$ 定义为：当 $k=0$ 时，$\varphi^k(x) = x$；当 $k > 0$ 时，$\varphi^k(x) = \varphi(\varphi^{k-1}(x))$。 - 在第一次操作 $2$ 中，为了使 $a_1 = a_2 = a_3 = a_4 = a_5$，我们可以将数列 $a$ 变为 $a' = [1, 1, 1, 1, 1]$，需要 $10$ 次变化。 - 在第二次操作 $2$ 中，为了使 $a_3 = a_4$，我们可以将数列 $a$ 变为 $a' = [8, 1, 2, 2, 7]$，需要 $2$ 次变化。 - 在操作 $1$ 后，数列 $a$ 变为 $a = [4, 1, 2, 3, 7]$。 - 在第三次操作 $2$ 中，为了使 $a_3 = a_4$，我们可以将数列 $a$ 变为 $a' = [4, 1, 2, 2, 7]$，需要 $1$ 次变化。