子数组最大公约数查询 题解

思路

固定右端点时，以它结尾的子数组 GCD 只会在加入新元素后取旧 GCD 与新元素的最大公约数，且不同值个数为 $O(\log A)$。

做法

子任务 1：平方枚举

枚举左端点并向右扩展，维护当前 GCD，将每个子数组计入哈希表。

子任务 2：全相等

若所有元素都是 $v$，全部 $n(n+1)/2$ 个子数组 GCD 都是 $v$。

子任务 3：压缩 GCD 状态

维护所有以当前位置结尾的子数组，按 GCD 合并相邻等值状态。把每个状态的数量累加进全局哈希表，最后 $O(1)$ 回答查询。

正确性证明

引理 1 更新后状态表准确表示所有以当前位置结尾的子数组 GCD 及数量。

证明 单元素子数组贡献新值；其余子数组均由上一位置结尾的子数组追加当前元素得到，GCD 更新为两者最大公约数。合并只汇总相同 GCD，不改变计数。∎

引理 2 全局表中每个 GCD 的计数等于具有该 GCD 的全部子数组数。

证明 每个非空子数组有唯一右端点，按引理 1 在处理该右端点时恰贡献一次。∎

定理 每个查询输出正确。

证明 由引理 2，全局表精确记录所有子数组按 GCD 分类的数量，查询直接读取对应项。∎

复杂度

时间复杂度 $O(n\log A+q)$，空间复杂度 $O(n\log A)$。