题目简述

给定正整数 $n$ 和长为 $n$ 的正整数序列 $a$。对于正整数 $x$，定义$\newcommand{dfrac}[2]{\displaystyle\frac{#1}{#2}}$

$$f(x)=\begin{cases}0&(x>n)\\f(x+\gcd(x,a_x))+a_x&(x\leq n)\end{cases}$$

现有 $q$ 次操作，分为两类：

• 1 l r c：将所有满足 $l\leq i\leq r$ 的 $a_i$ 的值乘以 $c$。
• 2 x：查询 $f(x)$ 对 $998244353$ 取模的值。

做法解析

做法的核心是分块。将序列分为长度为 $B$ 的一些块，并维护块内每个位置不断向后跳时第一次跳出块时对应的位置和这个过程中 $a_x$ 的总和，则可以 $O\left(\dfrac{n}{B}\right)$ 的处理一次查询。修改虽然是区间修改，但维护新的跳到的位置时，$\gcd(x,a_x)$ 的改变次数最多是 $x$ 质因子分解后对应幂次的总和，可以说明总的改变次数是 $O(n\log\log n)$ 的，因此可以用 set 对每个质数维护还可能被修改的位置，每次修改时暴力重构整个块；而对于维护一路上的权值和，可以对整块的修改打标记、散块的修改直接暴力，复杂度为 $O\left(B+\dfrac{n}{B}\right)$。因此总的复杂度大致为 $O\left(q\left(B+\dfrac{n}{B}\right)+n\log\log n\cdot (B+\log n)\right)$，综合分析常数和理论结果，大致取 $B=300$ （差不多是 $\dfrac{n}{\sqrt3}$）时最优。

时限给了 $4\text{s}$，实际上 std 取 $B=300$ 需要跑大约 $1.3\text{s}$，取 $B=500$ 也只需要大约 $2\text{s}$，所以应该是完全不卡常的。