Hi, story 题解

Gold14526 · 2026-07-07 08:37:15 · 题解

考虑只有全局加法的情况。此时，相当于每次给定一个 x，并询问所有 a_i+b_i \cdot x 的 \gcd。考虑将所有的 \gcd 写成 \gcd(kx+b,c) 的形式。我们发现，可以对 k_1x+b_1 和 k_2x+b_2 中的 k 执行欧几里得算法，同时维护 b。这样就可以合并两个 \gcd(kx+b,c)。因此，对于区间修改和区间查询，可以使用线段树来维护每个节点的这些信息。

可以发现，合并 n 个 \gcd(kx+b,c) 的复杂度实际上是 O(n+\log V)，因此单次线段树操作的复杂度为 O(\log n+\log V)，总时间复杂度为 O(n\log V+q\log n+q\log V)。