Li Hua хочет решить задачу о \(\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)\).
Каждая операция второго типа является независимой, то есть массив не изменяется.
Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.
\(^\dagger\) \(\gcd(x,y)\) обозначает наибольший общий делитель (НОД) целых чисел \(x\) и \(y\).
\(^\ddagger\) Выражение \([\textrm{cond}]\) равно \(1\), если условие \(\textrm{cond}\) верно, и \(0\) в противном случае.
Примечание
Обозначим \(\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\) изменение.