线段树二分

修改操作可以很简单的在线段树上打标记即可。

常规做法直接二分 R 然后区间查询 gcd，复杂度是仨log。

upded：其实也是俩log，线段树查询区间gcd是单 log。

注意到你会将区间拆分成 log 个子区间，直接查询他们的 gcd 即可，直接查询为什么不会多乘个 log 呢。

注意到对两个数 \(x,y\) 做 gcd 分为两种情况。

1.一个是另一个的倍数，此时做 gcd 是 \(O(1)\) 的

2.不存在一个是另一个的倍数，此时他们的 gcd 至少为两者较小的那个数的一半，最坏情况也就是两者为斐波那契数列的相邻两项，一次gcd要log，但是以后每一次gcd就会变成 \(O(1)\)，所以均摊下来查询的时候不会直接多乘个 log

高端的做法是，先转换求最小的 R 满足区间 gcd \(\le k\)

维护一个 \(cur\) 表示当前的 gcd，从左往右找到线段树上左端点 \(\ge L\) 的区间。

如果区间 gcd 和 \(cur\) 的gcd 大于 \(k\)，就继续往右找下一个区间。

否则就在当前区间递归，先考虑左儿子，如果gcd 大于 k 就向右儿子递归，否则向左儿子递归。

每次向右找区间最坏情况是找了 log 个区间，然后只会进入一个区间进行递归，递归复杂度也是单 log，再带上 gcd 的复杂度就是俩 log