CF1797E.Li Hua and Array

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) of integers $x$ and $y$.

$^\ddagger$ The notation $[\textrm{cond}]$ equals $1$ if the condition $\textrm{cond}$ is true, and $0$ otherwise.

李华想解决一个关于欧拉函数 $\varphi$ 的问题。请回忆：$\varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]$。$^{\dagger,\ddagger}$

他有一个序列 $a_1,a_2,\cdots,a_n$，并要执行 $m$ 个操作：

• “1 $l$ $r$”（$1\le l\le r\le n$）——对每个 $x\in[l,r]$，将 $a_x$ 替换为 $\varphi(a_x)$。
• “2 $l$ $r$”（$1\le l\le r\le n$）——求出使 $a_l=a_{l+1}=\cdots=a_r$ 所需的最少变换次数。每次变换中，他选择一个 $x\in[l,r]$，将 $a_x$ 替换为 $\varphi(a_x)$。此类操作相互独立，即数组实际并不发生改变。

假设你是李华，请解决该问题。

$^\dagger$ $\gcd(x,y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD）。

$^\ddagger$ 记号 $[\textrm{cond}]$ 在条件 $\textrm{cond}$ 成立时取值为 $1$，否则为 $0$。

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.

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 10^{5}$）—— 分别表示数组的元素个数和需要处理的操作个数。

第二行包含 $n$ 个整数 $a_{1},a_{2},\cdots ,a_{n}$（$1\le a_{i}\le 5\cdot 10^{6}$）—— 数组的元素。

接下来 $m$ 行，每行包含三个整数 $t_{i},l_{i},r_{i}$（$t_i\in\{1,2\},1\le l_i\le r_i\le n$）—— 第 $i$ 个操作。

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

对于每个“2 $l$ $r$”，在单独一行中输出答案。

Denote $\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k \gt 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^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k \gt 0\end{cases}$。

初始时，$a=[8,1,6,3,7]$。

为使 $a_1=a_2=a_3=a_4=a_5$，可将 $a$ 变为 $a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$，共需 $3+0+2+2+3=10$ 次变换。

为使 $a_3=a_4$，可将 $a$ 变为 $a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$，共需 $0+0+1+1+0=2$ 次变换。

执行操作 “1 $1$ $3$” 后，$a$ 变为 $a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$。

为使 $a_3=a_4$，可将 $a$ 变为 $a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$，共需 $0+0+0+1+0=1$ 次变换。