CF1797E Li Hua and Array

李华想要解决一个关于 $ \varphi $ —— 欧拉函数的问题。请回忆，$ \varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1] $。 他有一个序列 $ 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 $ 的最大公约数。 $^\ddagger$ 记号 $ [\textrm{cond}] $ 当条件 $ \textrm{cond} $ 成立时为 $ 1 $，否则为 $ 0 $。

第一行包含两个整数 $ 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 $ 次操作。

对于每个 “2 $ l $ $ r $” 操作，输出一行答案。

记 $ \varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 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 $ 次变化。 由 ChatGPT 4.1 翻译