记 $c_i=\gcd(i,a_i)$，操作二实际上就是给定初始的 $x$，每次令 $x\to c_x+x$，问跳出序列的路径上所有 $a_x$ 之和。

这个形式非常像 [HNOI 2010] 弹飞绵羊 这道题，实际上可以直接照搬分块做法，先将序列分块。

设 $f_i$ 表示从 $i$ 出发跳出快后到达那个位置，$g_i$ 表示从 $i$ 跳到 $f_i$ 的路径权值和。

假设 $i$ 所在的块的右边界为 $r$，则分情况。

1. 若 $i+c_i>r$：$f_i=i+c_i,g_i=a_i+w_i$。

2. 若 $i+c_i\le r$：$f_i=f_{i+c_i},g_i=a_i+g_{i+c_i}$。

注意单点修改整个块都要重构，所以单点修改的复杂度为 $O(B)$。

回到本题，查询的复杂度是显然的 $O\left(\frac{n}{B}\right)$，考虑如何修改。

不难发现，$c_i$ 在修改过程中只会不断增大趋近于 $i$，每次增大都会乘上一个数，均摊分析可以知道所有 $c_i$ 的变化次数不超过 $1\sim n$ 的质因子个数之和，即 $n\log n$。

所以每次要找到哪个数要单点修改后，直接暴力重构块即可，然后用分块维护区间 $a_i\gets a_i\times c$ 的操作。这一部分的复杂度为 $O(nB\log n)$。

问题在于，如何快速找到哪个数要单点修改，记 $b_i=\frac{i}{c_i}$。我最初的做法是每个块记录这个块 $u$ 所有 $b_i$ 每个具体质因子 $x$ 的和记为 $p_{u,x}$，修改时，先将 $c$ 拆成 $\log n$ 个区间乘质因子的操作，对于第 $i$ 个块乘质因子 $x$，则判断 $p_{i,x}$ 取值，若大于 $0$，则暴力修改块，反之则跳过。

最终的时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}\log V\right)$，空间复杂度为 $O(nB)$，大概取 $B=500$ 左右最快，只能在 LOJ 通过，常数太大了。

其实有一种更简单的区间找数操作，对于质数 $x$ 单独开一个 set，若 $b_i$ 有 $x$ 为质因子，则在 set 中插入 $i$。每次修改 $[l,r]$，直接暴力找 $[l,r]$ 里所有的数，每个数只修改 $c_i,b_i$，最后将有单点修改操作的块重构，注意维护此时的 set。

这样此时找数的时间复杂度也是可以均摊的，时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}+n\log^2n\right)$，此时 $B=\sqrt{\frac{n}{\log n}}$ 最优，大概在 $n=200\sim 300$ 的时候跑的比较快，且空间复杂度为 $O(n)$。已经可以通过 COGS 的测试了。