P11527 [THUPC 2025 初赛] waht 先生的法阵

由于洛谷评测机太慢，$4s\to 5s$。

waht 先生是一名法力强大的魔法师。 waht 先生为了增强自己的法力，设置了一个法阵。这个法阵中共有 $n$ 块魔法石，它们从左到右依次排成一列；并且从左数第 $i$ 块魔法石的编号为 $i$，其法力值初始为 $a_i$。 waht 先生可以获取一些魔法石的法力。然而由于这个法阵的特殊性质，在获取法力时，waht 先生必须先选择一块魔法石；并且一旦第 $x$ 块魔法石被选，接下来必须再选第 $x+\gcd(x,a_x)$ 块魔法石（这里 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数），直到 $x+\gcd (x,a_x)>n$ 时 waht 先生会立即停止本次法力获取的过程。waht 先生获取的法力将会是过程中所选的所有魔法石的法力值之和。 waht 先生会对这个法阵进行 $q$ 次操作。具体的，有以下两类操作： - waht 先生选择两个数 $l,r\;(1\leq l\leq r\leq n)$，对区间 $[l,r]$ 中的所有魔法石施加法术，使得它们的法力值全部乘以 $c$。具体的，对于所有满足 $l\leq i\leq r$ 的 $i$，将 $a_i$ 的值修改为 $c\cdot a_i$。 - waht 先生选择第 $x$ 块魔法石，并按照上述的规则获取法力。 每当 waht 先生选择某一块魔法石来获取法力时，你都需要帮他计算出他到底获得了多少法力。由于答案可能很大，你只需要求出答案对 $998244353$ 取模的结果。

第一行输入两个正整数 $n,q\;(1\leq n,q\leq 2.5\times 10^5)$，表示法阵中魔法石的数量和操作次数。 接下来一行，输入 $n$ 个正整数，其中第 $i$ 个为 $a_i\;(1\leq a_i

每当进行一次操作 $2$ 时，输出一行一个正整数，表示所要查询的答案对 $998244353$ 取模的值。

第一次操作，将区间 $[2,6]$ 中的魔法石的法力值乘以 $2$，法力值序列变为 $1,2,2,2,2,2,1$； 第二次操作，waht 先生选择第 $1$ 块魔法石，则编号为 $1,2,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $7$； 第三次操作，将区间 $[3,5]$ 中的魔法石的法力值乘以 $5$，法力值序列变为 $1,2,10,10,10,2,1$； 第四次操作，waht 先生选择第 $3$ 块魔法石，则编号为 $3,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $22$； 第五次操作，将区间 $[2,7]$ 中的魔法石的法力值乘以 $3$，法力值序列变为 $1,6,30,30,30,6,3$； 第六次操作，waht 先生选择第 $3$ 块魔法石，则编号为 $3,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $36$； 第七次操作，waht 先生选择第 $2$ 块魔法石，则编号为 $2,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $42$。 #### 题目来源 来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。 题解等资源可在 查看。