题解：P17112 「FAOI-R13」Hi, story

· · 题解

感觉应该很经典但咱还是不会……

不难想到把每个数描述成 k_ix+b_i 的形式。

对于这种数求 \gcd 是有性质的：对 k_i 做辗转相除，中途顺带维护 b_i 的变化，就可以写成 \gcd(kx+b,c) 的形式。合并这个东西也是一样的。

现在区间加，x 不一样了。可以把 x 看作懒标记，下传懒标记的操作就是 b\longleftarrow b+kx。

复杂度分析后面再说，反正超不过 O(n\log n\log V)。

然后是常数层面的优化。

注意到 k 是固定的，故辗转相除的过程也是固定的。考虑将系数记下来，pushup 的时候就只需要算 c 的 \gcd 了。

有个科技叫 Binary gcd，跑得会快很多。

复杂度的话考虑经典结论 n 个数求 \gcd 的复杂度是 O(n+\log V) 的。

故其实是单 \log 的。

代码有需求私，除了出题人 2200 分的提交以外是目前最优解。