E 直接每次拎出来最小的那个然后给所有数取个 gcd 即可。
然后如果全局 gcd 没变了直接算，均摊一下是 $O(n \log ^2 n)$ 的
by AfterFullStop @ 2024-09-21 00:38:38
@[AfterFullStop](/user/555065) 谢谢，发现我的做法错了一点
by ACPC @ 2024-09-21 00:41:17
C 先能往右边加就往右边加 $0/1$，加不动了说明这是一个后缀，然后往前加就行了。
by ForgotMe @ 2024-09-21 00:52:08
@[ForgotMe](/user/154560) 这个做法理论上不是最多能卡到 $2n+2$次询问吗
by Hexarhy @ 2024-09-21 00:58:18
@[AfterFullStop](/user/555065) 怎么证明？我赛时感觉错完了（）
by sbno333 @ 2024-09-21 01:03:07
C 省掉开头一位和最后一位的询问可以卡到 $2n$...
by Hexarhy @ 2024-09-21 01:09:42
@[sbno333](/user/416975) 完了我不会证了（
好像直接用邻项证是错的，但如果可以那就是对的了（
我再想想，看看明早能不能想出来
by AfterFullStop @ 2024-09-21 01:17:06
@[AfterFullStop](/user/555065) 为啥不能邻项啊，首先答案序列里面肯定没有平台，然后交换答案序列里面任意两项一定变劣啊。
by Shunpower @ 2024-09-21 01:30:52
你交换任意两项之后只有中间那个位置前缀 $\gcd$ 有变化，你换成那个地方的非最小 $\gcd$ 肯定变差。
by Shunpower @ 2024-09-21 01:32:48
@[Shunpower](/user/399150) 所以说哪些东西是能用邻项的，哪些是不能用的，感觉现在完全懵了。
像比如说 P4110 邻项就是错的。
by AfterFullStop @ 2024-09-21 07:08:33