← 返回题目列表

Codeforces · 1797/E

E. 李华与阵

中文机器翻译题面 查看原题

李华想要解决一个关于$$$\varphi$$$ 的问题——欧拉 totient 函数。请记住 $$$\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$$$。

输入

第一行包含两个整数 $$$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$$$”,在单独的行中输出答案。

示例

输入 #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)=\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$$$ 变化。