题解 P4108 [[HEOI2015]公约数数列]
感觉需要推导的东西还是比较多的.但是以后要记着看到奇怪的(?)数据范围时要想到分块.
这个题有一定的特点,就是两个表达式都是前缀形式.对于 $\gcd$ 而言,它一定是递减的,而且不同的数值最多只有 $O(\log a_i)$ 个,因为每次至少会变为原来的 $\frac 12$.因此产生变化的位置是可以考虑枚举的.
注意到询问是 $10000$ 的,不是很大.我们对原区间进行 $O(\sqrt n)$ 分块.
因为要找的是最小的,所以应该从前往后枚举.对于 $\gcd$ 整块不变的那些块,我们只需要找到其中是否存在异或前缀和恰好为 $x/\gcd$ 的.这一询问可