AC代码：

https://codeforces.com/contest/1797/submission/203226084

题意：

φ(x)表示小于或等于 x 的正整数中与 x 互质的数的数目。

我们有一个序列a1，a2，…，an，可以执行m个操作：

1. “1 l r”（1≤l≤r≤n）-对于每个x∈[l，r]，将ax变为φ（ax）。

2. “2 l r”（1≤l≤r≤n）-找出确保al=al+1=…=ar所需的最小变化次数。

在每次变化中，他选择一个x∈[l，r]，将ax变为φ（ax）。

这种类型的每个操作都是独立的，这意味着数组实际上不会改变。

题解：

数论 + 线段树